1,121 research outputs found
Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
No full textOne of the most fundamental problems in Computer Science is the Knapsack problem. Given a set of n items with different weights and values, it asks to pick the most valuable subset whose total weight is below a capacity threshold T. Despite its wide applicability in various areas in Computer Science, Operations Research, and Finance, the best known running time for the problem is O(T n). The main result of our work is an improved algorithm running in time O(TD), where D is the number of distinct weights. Previously, faster runtimes for Knapsack were only possible when both weights and values are bounded by M and V respectively, running in time O(nMV) [Pisinger, 1999]. In comparison, our algorithm implies a bound of O(n M^2) without any dependence on V, or O(n V^2) without any dependence on M. Additionally, for the unbounded Knapsack problem, we provide an algorithm running in time O(M^2) or O(V^2). Both our algorithms match recent conditional lower bounds shown for the Knapsack problem [Marek Cygan et al., 2017; Marvin Künnemann et al., 2017].
We also initiate a systematic study of general capacitated dynamic programming, of which Knapsack is a core problem. This problem asks to compute the maximum weight path of length k in an edge- or node-weighted directed acyclic graph. In a graph with m edges, these problems are solvable by dynamic programming in time O(k m), and we explore under which conditions the dependence on k can be eliminated. We identify large classes of graphs where this is possible and apply our results to obtain linear time algorithms for the problem of k-sparse Delta-separated sequences. The main technical innovation behind our results is identifying and exploiting concavity that appears in relaxations and subproblems of the tasks we consider
On the Size and the Approximability of Minimum Temporally Connected Subgraphs
No full textWe consider temporal graphs with discrete time labels and investigate the size and the approximability of minimum temporally connected spanning subgraphs. We present a family of minimally connected temporal graphs with n vertices and Omega(n^2) edges, thus resolving an open question of (Kempe, Kleinberg, Kumar, JCSS 64, 2002) about the existence of sparse temporal connectivity certificates. Next, we consider the problem of computing a minimum weight subset of temporal edges that preserve connectivity of a given temporal graph either from a given vertex r (r-MTC problem) or among all vertex pairs (MTC problem). We show that the approximability of r-MTC is closely related to the approximability of Directed Steiner Tree and that r-MTC can be solved in polynomial time if the underlying graph has bounded treewidth. We also show that the best approximation ratio for MTC is at least O(2^{log^{1-epsilon}(n)} and at most O(min{n^{1+epsilon},(Delta*M)^{2/3+epsilon}), for any constant epsilon > 0, where M is the number of temporal edges and Delta is the maximum degree of the underlying graph. Furthermore, we prove that the unweighted version of MTC is APX-hard and that MTC is efficiently solvable in trees and 2-approximable in cycles
High-spin states and band terminations in v 49
No full textHigh-spin states in 49 V have been studied through the 28 Si(28 Si, α3p) reaction using the EUROBALL γ-ray detector array. The 49 V level scheme has been extended up to 13.1 MeV including 21 new states. Both negative and positive parity states have been interpreted in the framework of theShell Model. The 27/2− and the 31/2+ band termination states have been observed in agreement with theoretical predictions.Fil: Rodrigues Ferreira Maltez, Dario Pablo. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Comisión Nacional de Energía Atómica. Gerencia del Área de Investigación y Aplicaciones No Nucleares. Gerencia Física (Centro Atómico Constituyentes). Proyecto Tandar; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Física; ArgentinaFil: Hojman, Daniel Leonardo. Comisión Nacional de Energía Atómica. Gerencia del Área de Investigación y Aplicaciones No Nucleares. Gerencia Física (Centro Atómico Constituyentes). Proyecto Tandar; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Lenzi, Silvia M.. Istituto Nazionale Di Fisica Nucleare.; Italia. Università di Padova; ItaliaFil: Cardona, Maria Angelica. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Comisión Nacional de Energía Atómica. Gerencia del Área de Investigación y Aplicaciones No Nucleares. Gerencia Física (Centro Atómico Constituyentes). Proyecto Tandar; Argentina. Universidad Nacional de San Martín. Escuela de Ciencia y Tecnología; ArgentinaFil: Fernea, Enrico. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Axiotis, M.. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Beck, C.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Bednarczyk, P.. Polish Academy of Sciences; ArgentinaFil: Bizzetti, P. G.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Bizzetti Sona, A. M.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Della Vedova, F.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Grebosz, J.. Polish Academy of Sciences; ArgentinaFil: Haas, F.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Kmiecik, M.. Polish Academy of Sciences; ArgentinaFil: Maj, A.. Polish Academy of Sciences; ArgentinaFil: Męczyński, W.. Polish Academy of Sciences; ArgentinaFil: Napoli, D. R.. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Nespolo, M.. Università di Padova; Italia. Istituto Nazionale Di Fisica Nucleare.; ItaliaFil: Papka, P.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Sánchez i Zafra, A.. Université de Strasbourg; Francia. Centre National de la Recherche Scientifique; FranciaFil: Styczen, J.. Polish Academy of Sciences; ArgentinaFil: Thummerer, S.. Alfred-Wegener-Institut, Helmholtz-Zentrum für Polar- und Meeresforschung; AlemaniaFil: Ziębliński, M.. Polish Academy of Sciences; Argentin
Fast and Simple Modular Subset Sum
No full textWe revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has providedasymptotically optimal algorithms for this problem under the Strong ExponentialTime Hypothesis. Koiliaris and Xu (SODA'17, TALG'19) gave a deterministicalgorithm running in time , which was later improved to randomized time by Axiotis et al. (SODA'19). In this work, wepresent two simple algorithms for the Modular Subset Sum problem running innear-linear time in , both efficiently implementing Bellman's iteration over. The first one is a randomized algorithm running in time, that is based solely on rolling hash and an elementarydata-structure for prefix sums; to illustrate its simplicity we provide a shortand efficient implementation of the algorithm in Python. Our second solution isa deterministic algorithm running in time , thatuses dynamic data structures for string manipulation. We further show that thetechniques developed in this work can also lead to simple algorithms for theAll Pairs Non-Decreasing Paths Problem (APNP) on undirected graphs, matchingthe asymptotically optimal running time of provided in therecent work of Duan et al. (ICALP'19).<br
Faster Deterministic Modular Subset Sum
No full textWe consider the Modular Subset Sum problem: given a multiset X of integers from ℤ_m and a target integer t, decide if there exists a subset of X with a sum equal to t (mod m). Recent independent works by Cardinal and Iacono (SOSA'21), and Axiotis et al. (SOSA'21) provided simple and near-linear algorithms for this problem. Cardinal and Iacono gave a randomized algorithm that runs in (m log m) time, while Axiotis et al. gave a deterministic algorithm that runs in (m polylog m) time. Both results work by reduction to a text problem, which is solved using a dynamic strings data structure.
In this work, we develop a simple data structure, designed specifically to handle the text problem that arises in the algorithms for Modular Subset Sum. Our data structure, which we call the shift-tree, is a simple variant of a segment tree. We provide both a hashing-based and a deterministic variant of the shift-trees.
We then apply our data structure to the Modular Subset Sum problem and obtain two algorithms. The first algorithm is Monte-Carlo randomized and matches the (m log m) runtime of the Las-Vegas algorithm by Cardinal and Iacono. The second algorithm is fully deterministic and runs in (m log m ⋅ α(m)) time, where α is the inverse Ackermann function
Algorithms for Subset Sum using linear sketching
No full textThesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from PDF version of thesis.Includes bibliographical references (pages 41-43).Given n positive integers, the Modular Subset Sum problem asks if a subset adds up to a given target t modulo a given integer m. This is a natural generalization of the Subset Sum problem (where m = + [infinity symbol]) with ties to additive combinatorics and cryptography. The non-modular case was long known to be NP-complete but to admit pseudo-polynomial time algorithms and, recently, algorithms running in near-linear pseudo-polynomial time were developed [9, 211. For the modular case, however, the best known algorithm by Koiliaris and Xu [21] runs in time 0̃ (m⁵/⁴). In this thesis we tackle this problem by devising a faster algorithm for the Modular Subset Sum problem, running in 0̃(m) randomized time, which matches a recent conditional lower bound of [1] based on the Strong Exponential Time Hypothesis. Interestingly, in contrast to most previous results on Subset Sum, our algorithm does not use the Fast Fourier Transform. Instead, it is able to simulate the "textbook" Dynamic Programming algorithm much faster, using ideas from linear sketching. This is one of the first applications of sketching-based techniques to obtain fast algorithms for exact combinatorial problems in an offline setting.by Kyriakos Axiotis.S.M.S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Scienc
The novel mTOR inhibitor RAD001 (Everolimus) induces antiproliferative effects in human pancreatic neuroendocrine tumor cells
No full textBackground/Aim: Tumors exhibiting constitutively activated PI(3) K/Akt/mTOR signaling are hypersensitive to mTOR inhibitors such as RAD001 (everolimus) which is presently being investigated in clinical phase II trials in various tumor entities, including neuroendocrine tumors (NETs). However, no preclinical data about the effects of RAD001 on NET cells have been published. In this study, we aimed to evaluate the effects of RAD001 on BON cells, a human pancreatic NET cell line that exhibits constitutively activated PI(3) K/Akt/mTOR signaling. Methods: BON cells were treated with different concentrations of RAD001 to analyze its effect on cell growth using proliferation assays. Apoptosis was examined by Western blot analysis of caspase-3/PARP cleavage and by FACS analysis of DNA fragmentation. Results: RAD001 potently inhibited BON cell growth in a dose-dependent manner which was dependent on the serum concentration in the medium. RAD001-induced growth inhibition involved G0/G1-phase arrest as well as induction of apoptosis. Conclusion: In summary, our data demonstrate antiproliferative and apoptotic effects of RAD001 in NET cells in vitro supporting its clinical use in current phase II trials in NET patients. Copyright (c) 2007 S. Karger AG, Basel
Satellite Radio Interface and Radio Resource Management Strategy for the Delivery of Multicast/Broadcast Services via an Integrated Satellite-Terrestrial System
No full text
- …
