×
Axiotis, Kyriakos; Tzamos, Christos

Capacitated dynamic programming: faster knapsack and graph algorithms. (English) Zbl 1552.68373

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 19, 13 p. (2019).
Summary: One of the most fundamental problems in Computer Science is the . 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, , and Finance, the best known running time for the problem is \(O(Tn)\). 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)\) [D. Pisinger, J. Algorithms 33, No. 1, 1–14 (1999; Zbl 0951.90047)]. In comparison, our algorithm implies a bound of \(O(nM^2)\) without any dependence on \(V\), or \(O(nV^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 [M. Cygan et al., LIPIcs – Leibniz Int. Proc. Inform. 80, Article 22, 15 p. (2017; Zbl 1441.68070); M. Künnemann et al., ibid. 80, Article 21, 15 p. (2017; Zbl 1441.68078)].
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 . In a graph with \(m\) edges, these problems are solvable by dynamic programming in time \(O(km)\), 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.
For the entire collection see [Zbl 1414.68003].

Cited in 1 Review
Cited in 12 Documents

MSC:

68W05 Nonnumerical algorithms
05C85 Graph algorithms (graph-theoretic aspects)
68W40 Analysis of algorithms
90C27 Combinatorial optimization
90C39 Dynamic programming

Keywords:

knapsack; fine-grained complexity; dynamic programming

Citations:

Zbl 0951.90047; Zbl 1441.68070; Zbl 1441.68078
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Alok Aggarwal, Maria M Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1-4):195-208, 1987. · Zbl 0642.68078
[2] Alok Aggarwal, Baruch Schieber, and Takeshi Tokuyama. Finding a minimum-weightk-link path in graphs with the concave monge property and applications. Discrete & Computational Geometry, 12(3):263-280, 1994. · Zbl 0819.68084
[3] Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2215-2229. SIAM, 2017. · Zbl 1410.68394
[4] MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein. Fast algorithms for knapsack via convolution and prediction. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 1269-1282, 2018. · Zbl 1427.68376
[5] WW Bein, LL Larmore, and JK Park. The d-edge shortest-path problem for a Monge graph. Technical report, Sandia National Labs., Albuquerque, NM (United States), 1992.
[6] Richard Bellman. Dynamic Programming (DP). Princeton University Press, 1957. · Zbl 0077.13605
[7] Karl Bringmann. A near-linear pseudopolynomial time algorithm for subset sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1073-1084. Society for Industrial and Applied Mathematics, 2017. · Zbl 1423.90210
[8] Henning Bruhn and Oliver Schaudt. Fast Algorithms for Delta-Separated Sparsity Projection. arXiv preprint, 2017. arXiv:1712.06706. · Zbl 1348.05187
[9] Timothy M Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1246-1255. Society for Industrial and Applied Mathematics, 2016. · Zbl 1410.68286
[10] Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (min, +)-Convolution. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 22:1-22:15, 2017. · Zbl 1441.68070
[11] Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the steinitz lemma. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 808-816. Society for Industrial and Applied Mathematics, 2018. · Zbl 1410.90128
[12] Chinmay Hegde, Marco F Duarte, and Volkan Cevher. Compressive sensing recovery of spike trains using a structured sparsity model. In SPARS’09-Signal Processing with Adaptive Sparse Structured Representations, 2009.
[13] Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. arXiv preprint, 2018. arXiv:1803.04744. · Zbl 1415.90041
[14] Konstantinos Koiliaris and Chao Xu. A faster pseudopolynomial time algorithm for subset sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1062-1072. SIAM, 2017. · Zbl 1422.90046
[15] Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Com-plexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 21:1-21:15, 2017. · Zbl 1441.68078
[16] Aleksander Mądry, Slobodan Mitrović, and Ludwig Schmidt. A Fast Algorithm for Separated Sparsity via Perturbed Lagrangians. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pages 20-28, 2018.
[17] David Pisinger. Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithms, 33(1):1-14, 1999. · Zbl 0951.90047
[18] Baruch Schieber. Computing a minimum weightk-link path in graphs with the concave monge property. Journal of Algorithms, 29(2):204-222, 1998. · Zbl 0916.68066
[19] Robert Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9(3):418-425, 1988. · Zbl 0651.68093
[20] Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 664-673. ACM, 2014. · Zbl 1315.68282
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.