Document Open Access Logo

Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms

Authors Kyriakos Axiotis, Christos Tzamos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.19.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Kyriakos Axiotis
  • MIT, Cambridge, MA, USA
Christos Tzamos
  • University of Wisconsin-Madison, USA

Acknowledgements

We are grateful to Arturs Backurs for insightful discussions that helped us improve this work.

Cite As Get BibTex

Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.19

Abstract

One 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
Keywords
  • Knapsack
  • Fine-Grained Complexity
  • Dynamic Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  6. Richard Bellman. Dynamic Programming (DP). Princeton University Press, 1957. Google Scholar
  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. Google Scholar
  8. Henning Bruhn and Oliver Schaudt. Fast Algorithms for Delta-Separated Sparsity Projection. arXiv preprint, 2017. URL: http://arxiv.org/abs/1712.06706.
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  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. Google Scholar
  13. Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. arXiv preprint, 2018. URL: http://arxiv.org/abs/1803.04744.
  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. Google Scholar
  15. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity 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. Google Scholar
  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. Google Scholar
  17. David Pisinger. Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithms, 33(1):1-14, 1999. Google Scholar
  18. Baruch Schieber. Computing a minimum weightk-link path in graphs with the concave monge property. Journal of Algorithms, 29(2):204-222, 1998. Google Scholar
  19. Robert Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9(3):418-425, 1988. Google Scholar
  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. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact