Document Open Access Logo

Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

Authors Karl Bringmann, Alejandro Cassis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.31.pdf
  • Filesize: 0.85 MB
  • 21 pages

Document Identifiers

Author Details

Karl Bringmann
  • Universität des Saarlandes, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Alejandro Cassis
  • Universität des Saarlandes, Saarland Informatics Campus, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Funding

This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979).

Cite As Get BibTex

Karl Bringmann and Alejandro Cassis. Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.31

Abstract

We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack:  
- Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time Õ(n + min{n ⋅ OPT, n ⋅ W, OPT², W²}) [Bellman '57], where n is the number of items, W is the weight budget, and OPT is the optimal profit. We present an algorithm running in time Õ(n + (W + OPT)^{1.5}). This improves the running time in case n,W,OPT are roughly equal. 
- Exact Algorithm for Unbounded Knapsack: Unbounded Knapsack has known algorithms running in time Õ(n + min{n ⋅ p_max, n ⋅ w_max, p_max², w_max²}) [Axiotis, Tzamos '19, Jansen, Rohwedder '19, Chan, He '22], where n is the number of items, w_{max} is the largest weight of any item, and p_max is the largest profit of any item. We present an algorithm running in time Õ(n + (p_max + w_max)^{1.5}), giving a similar improvement as for 0-1-Knapsack.
- Approximating Unbounded Knapsack with Resource Augmentation: Unbounded Knapsack has a known FPTAS with running time Õ(min{n/ε, n + 1/ε²}) [Jansen, Kraft '18]. We study weak approximation algorithms, which approximate the optimal profit but are allowed to overshoot the weight constraint (i.e. resource augmentation). We present the first approximation scheme for Unbounded Knapsack in this setting, achieving running time Õ(n + 1/ε^{1.5}). Along the way, we also give a simpler FPTAS with lower order improvement in the standard setting. 
For all of these problem settings the previously known results had matching conditional lower bounds. We avoid these lower bounds in the approximation setting by allowing resource augmentation, and in the exact setting by analyzing the time complexity in terms of weight and profit parameters (instead of only weight or only profit parameters).
Our algorithms can be seen as reductions to Min-Plus-Convolution on monotone sequences with bounded entries. These structured instances of Min-Plus-Convolution can be solved in time O(n^1.5) [Chi, Duan, Xie, Zhang '22] (in contrast to the conjectured n^{2-o(1)} lower bound for the general case). We complement our results by showing reductions in the opposite direction, that is, we show that achieving our results with the constant 1.5 replaced by any constant < 2 implies subquadratic algorithms for Min-Plus-Convolution on monotone sequences with bounded entries.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Knapsack
  • Approximation Schemes
  • Fine-Grained Complexity
  • Min-Plus Convolution

Metrics

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

Related Versions

References

  1. Noga Alon, Zvi Galil, Oded Margalit, and Moni Naor. Witnesses for Boolean matrix multiplication and for shortest paths. In FOCS, pages 417-426. IEEE Computer Society, 1992. Google Scholar
  2. Noga Alon and Moni Naor. Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16(4/5):434-449, 1996. Google Scholar
  3. Kyriakos Axiotis and Christos Tzamos. Capacitated dynamic programming: Faster Knapsack and graph algorithms. In ICALP, volume 132 of LIPIcs, pages 19:1-19:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  4. Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better approximations for tree sparsity in nearly-linear time. In SODA, pages 2215-2229. SIAM, 2017. Google Scholar
  5. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Saeed Seddighin, and Cliff Stein. Fast algorithms for Knapsack via convolution and prediction. In STOC, pages 1269-1282. ACM, 2018. Google Scholar
  6. Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1957. Google Scholar
  7. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. Google Scholar
  8. Karl Bringmann. A near-linear pseudopolynomial time algorithm for Subset Sum. In SODA, pages 1073-1084. SIAM, 2017. Google Scholar
  9. Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams. Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product. SIAM J. Comput., 48(2):481-512, 2019. Google Scholar
  10. Karl Bringmann and Vasileios Nakos. A fine-grained perspective on approximating Subset sum and Partition. In SODA, pages 1797-1815. SIAM, 2021. Google Scholar
  11. Karl Bringmann and Philip Wellnitz. On near-linear-time algorithms for dense subset sum. In SODA, pages 1777-1796. SIAM, 2021. Google Scholar
  12. Michael R. Bussieck, Hannes Hassler, Gerhard J. Woeginger, and Uwe T. Zimmermann. Fast algorithms for the maximum convolution problem. Oper. Res. Lett., 15(3):133-141, 1994. Google Scholar
  13. Timothy M. Chan. Approximation schemes for 0-1 Knapsack. In SOSA, volume 61 of OASICS, pages 5:1-5:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  14. Timothy M. Chan and Sariel Har-Peled. Smallest k-enclosing rectangle revisited. In SoCG, volume 129 of LIPIcs, pages 23:1-23:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  15. Timothy M. Chan and Qizheng He. More on change-making and related problems. J. Comput. Syst. Sci., 124:159-169, 2022. Google Scholar
  16. Timothy M. Chan and Moshe Lewenstein. Clustered integer 3SUM via Additive Combinatorics. In STOC, pages 31-40. ACM, 2015. Google Scholar
  17. Timothy M. Chan and R. Ryan Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. ACM Trans. Algorithms, 17(1):2:1-2:14, 2021. Google Scholar
  18. Shucheng Chi, Ran Duan, Tianle Xie, and Tianyi Zhang. Faster min-plus product for monotone instances. In STOC. ACM, 2022. Google Scholar
  19. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, 2019. Google Scholar
  20. Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms, 16(1):5:1-5:14, 2020. Google Scholar
  21. Zvi Galil and Oded Margalit. An almost linear-time algorithm for the dense subset-sum problem. SIAM J. Comput., 20(6):1157-1189, 1991. Google Scholar
  22. V. S. Grinberg and S. V. Sevastyanov. Value of the Steinitz constant. Funktsional. Anal. i Prilozhen., 14(2):56-57, 1980. Google Scholar
  23. Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the Knapsack and Sum of Subset problems. J. ACM, 22(4):463-468, 1975. Google Scholar
  24. Klaus Jansen and Stefan Erich Julius Kraft. A faster FPTAS for the Unbounded Knapsack problem. Eur. J. Comb., 68:148-174, 2018. Google Scholar
  25. Klaus Jansen and Lars Rohwedder. On integer programming and convolution. In ITCS, volume 124 of LIPIcs, pages 43:1-43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  26. Ce Jin and Hongxun Wu. A simple near-linear pseudopolynomial time randomized algorithm for Subset Sum. In SOSA, volume 69 of OASICS, pages 17:1-17:6. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  27. Hans Kellerer and Ulrich Pferschy. Improved dynamic programming in connection with an FPTAS for the knapsack problem. J. Comb. Optim., 8(1):5-11, 2004. Google Scholar
  28. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the fine-grained complexity of one-dimensional dynamic programming. In ICALP, volume 80 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  29. Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese. On lower bounds for the maximum consecutive subsums problem and the (min, +)-convolution. In ISIT, pages 1807-1811. IEEE, 2014. Google Scholar
  30. Eugene L. Lawler. Fast approximation algorithms for Knapsack problems. Math. Oper. Res., 4(4):339-356, 1979. Google Scholar
  31. Jiří Matoušek. Thirty-three miniatures: Mathematical and Algorithmic applications of Linear Algebra. American Mathematical Society Providence, RI, 2010. Google Scholar
  32. Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. A subquadratic approximation scheme for Partition. In SODA, pages 70-88. SIAM, 2019. Google Scholar
  33. David Pisinger. Linear time algorithms for Knapsack problems with bounded weights. J. Algorithms, 33(1):1-14, 1999. Google Scholar
  34. Adam Polak, Lars Rohwedder, and Karol Wegrzycki. Knapsack and Subset Sum with small items. In ICALP, volume 198 of LIPIcs, pages 106:1-106:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  35. Raimund Seidel. On the All-Pairs-Shortest-Path problem in unweighted undirected graphs. J. Comput. Syst. Sci., 51(3):400-403, 1995. Google Scholar
  36. Ernst Steinitz. Bedingt konvergente Reihen und konvexe Systeme. Journal für die reine und angewandte Mathematik, 143:128-176, 1913. URL: http://eudml.org/doc/149403.
  37. R. Ryan Williams. Faster All-Pairs Shortest Paths via circuit complexity. SIAM J. Comput., 47(5):1965-1985, 2018. 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