LIPIcs.ICALP.2019.76.pdf
- Filesize: 455 kB
- 14 pages
Document
An Improved FPTAS for 0-1 Knapsack
Author
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Acknowledgements
Part of this research was done while visiting Harvard University. I would like to thank Professor Jelani Nelson for introducing this problem to me, advising this project, and giving many helpful comments on my writeup.
Cite AsGet BibTex
Ce Jin. An Improved FPTAS for 0-1 Knapsack. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 76:1-76:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.76
https://doi.org/10.4230/LIPIcs.ICALP.2019.76
Abstract
The 0-1 knapsack problem is an important NP-hard problem that admits fully polynomial-time approximation schemes (FPTASs). Previously the fastest FPTAS by Chan (2018) with approximation factor 1+epsilon runs in O~(n + (1/epsilon)^{12/5}) time, where O~ hides polylogarithmic factors. In this paper we present an improved algorithm in O~(n+(1/epsilon)^{9/4}) time, with only a (1/epsilon)^{1/4} gap from the quadratic conditional lower bound based on (min,+)-convolution. Our improvement comes from a multi-level extension of Chan’s number-theoretic construction, and a greedy lemma that reduces unnecessary computation spent on cheap items.
Subject Classification
ACM Subject Classification
- Theory of computation → Algorithm design techniques
Keywords
- approximation algorithms
- knapsack
- subset sum
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2(1):195-208, November 1987. URL: http://dx.doi.org/10.1007/BF01840359.
- David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Pǎtraşcu, and Perouz Taslakian. Necklaces, Convolutions, and X+Y. Algorithmica, 69(2):294-314, June 2014. URL: http://dx.doi.org/10.1007/s00453-012-9734-3.
- Timothy M. Chan. Approximation Schemes for 0-1 Knapsack. In Proceedings of the 1st Symposium on Simplicity in Algorithms (SOSA), pages 5:1-5:12, 2018. URL: http://dx.doi.org/10.4230/OASIcs.SOSA.2018.5.
- Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1246-1255, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch87.
- Marek Cygan, Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. On Problems Equivalent to (Min,+)-Convolution. ACM Trans. Algorithms, 15(1):14:1-14:25, January 2019. URL: http://dx.doi.org/10.1145/3293465.
- Oscar H. Ibarra and Chul E. Kim. Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems. Journal of the ACM (JACM), 22(4):463-468, October 1975. URL: http://dx.doi.org/10.1145/321906.321909.
- Klaus Jansen and Stefan E.J. Kraft. A faster FPTAS for the Unbounded Knapsack Problem. European Journal of Combinatorics, 68:148-174, 2018. URL: http://dx.doi.org/10.1016/j.ejc.2017.07.016.
- Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Springer US, 1972. URL: http://dx.doi.org/10.1007/978-1-4684-2001-2_9.
- Hans Kellerer, Renata Mansini, Ulrich Pferschy, and Maria Grazia Speranza. An efficient fully polynomial approximation scheme for the Subset-Sum Problem. Journal of Computer and System Sciences, 66(2):349-370, 2003. URL: http://dx.doi.org/10.1016/S0022-0000(03)00006-0.
- Hans Kellerer and Ulrich Pferschy. A New Fully Polynomial Time Approximation Scheme for the Knapsack Problem. Journal of Combinatorial Optimization, 3(1):59-71, July 1999. URL: http://dx.doi.org/10.1023/A:1009813105532.
- Hans Kellerer and Ulrich Pferschy. Improved Dynamic Programming in Connection with an FPTAS for the Knapsack Problem. Journal of Combinatorial Optimization, 8(1):5-11, March 2004. URL: http://dx.doi.org/10.1023/B:JOCO.0000021934.29833.6b.
- Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 21:1-21:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.21.
- Eugene L. Lawler. Fast Approximation Algorithms for Knapsack Problems. Mathematics of Operations Research, 4(4):339-356, 1979. URL: http://dx.doi.org/10.1287/moor.4.4.339.
- Marcin Mucha, Karol Węgrzycki, and Michał Włodarczyk. Subquadratic Approximation Scheme for Partition. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 70-88, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.5.
- Donguk Rhee. Faster fully polynomial approximation schemes for knapsack problems. Master’s thesis, Massachusetts Institute of Technology, 2015. URL: http://hdl.handle.net/1721.1/98564.
- Ryan Williams. Faster All-pairs Shortest Paths via Circuit Complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 664-673, 2014. URL: http://dx.doi.org/10.1145/2591796.2591811.