OASIcs.SOSA.2018.5.pdf
- Filesize: 494 kB
- 12 pages
Document
Approximation Schemes for 0-1 Knapsack
Author
-
Part of:
Volume:
1st Symposium on Simplicity in Algorithms (SOSA 2018)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-01-05
Cite As Get BibTex
Timothy M. Chan. Approximation Schemes for 0-1 Knapsack. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.5
Abstract
We revisit the standard 0-1 knapsack problem. The latest polynomial-time approximation scheme by Rhee (2015) with approximation factor 1+eps has running time near O(n+(1/eps)^{5/2}) (ignoring polylogarithmic factors), and is randomized. We present a simpler algorithm which achieves the same result and is deterministic.
With more effort, our ideas can actually lead to an improved time bound near O(n + (1/eps)^{12/5}), and still further improvements for small n.
Subject Classification
Keywords
- knapsack problem
- approximation algorithms
- optimization
- (min,+)-convolution
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195-208, 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 Patrascu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9734-3.
- Timothy M. Chan and Moshe Lewenstein. Clustered integer 3sum via additive combinatorics. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 31-40. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746568.
- Timothy M. Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1246-1255. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch87.
- Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On problems equivalent to (min, +)-convolution. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 22:1-22:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.22.
- 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. URL: http://dx.doi.org/10.1145/321906.321909.
- Klaus Jansen and Stefan Erich Julius Kraft. A faster FPTAS for the unbounded knapsack problem. In Zsuzsanna Lipták and William F. Smyth, editors, Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Verona, Italy, October 5-7, 2015, Revised Selected Papers, volume 9538 of Lecture Notes in Computer Science, pages 274-286. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-29516-9_23.
- Hans Kellerer, Renata Mansini, Ulrich Pferschy, and Maria Grazia Speranza. An efficient fully polynomial approximation scheme for the subset-sum problem. J. Comput. Syst. Sci., 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. J. Comb. Optim., 3(1):59-71, 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. J. Comb. Optim., 8(1):5-11, 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 Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.21.
- Eugene L. Lawler. Fast approximation algorithms for knapsack problems. Math. Oper. Res., 4(4):339-356, 1979. URL: http://dx.doi.org/10.1287/moor.4.4.339.
- M. J. Magazine and O. Oguz. A fully polynomial approximation algorithm for the 0-1 knapsack problem. Europ. J. Oper. Res., 123:325-332, 2000. URL: http://dx.doi.org/10.1016/0377-2217(84)90286-8.
- Donguk Rhee. Faster fully polynomial approximation schemes for knapsack problems. Master’s thesis, MIT, 2015. URL: https://dspace.mit.edu/bitstream/handle/1721.1/98564/920857251-MIT.pdf.
- Sartaj Sahni. Approximate algorithms for the 0/1 knapsack problem. J. ACM, 22(1):115-124, 1975. URL: http://dx.doi.org/10.1145/321864.321873.
- Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 664-673. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591811.