OASIcs.SOSA.2019.17.pdf
- Filesize: 409 kB
- 6 pages
Document
A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
Authors
-
Part of:
Volume:
2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Series: Open Access Series in Informatics (OASIcs) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-01-08
Cite As Get BibTex
Ce Jin and Hongxun Wu. A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.SOSA.2019.17
Abstract
Given a multiset S of n positive integers and a target integer t, the Subset Sum problem asks to determine whether there exists a subset of S that sums up to t. The current best deterministic algorithm, by Koiliaris and Xu [SODA'17], runs in O~(sqrt{n}t) time, where O~ hides poly-logarithm factors. Bringmann [SODA'17] later gave a randomized O~(n + t) time algorithm using two-stage color-coding. The O~(n+t) running time is believed to be near-optimal.
In this paper, we present a simple and elegant randomized algorithm for Subset Sum in O~(n + t) time. Our new algorithm actually solves its counting version modulo prime p>t, by manipulating generating functions using FFT.
Subject Classification
Keywords
- subset sum
- formal power series
- FFT
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for subset sum and bicriteria path. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019. To appear. URL: http://arxiv.org/abs/1704.04546.
-
Richard E. Bellman. Dynamic programming. Princeton University Press, 1957.
- Richard P. Brent. Multiple-precision zero-finding methods and the complexity of elementary function evaluation. In Analytic Computational Complexity, pages 151-176. Elsevier, 1976. URL: http://dx.doi.org/10.1016/B978-0-12-697560-4.50014-9.
- Karl Bringmann. A near-linear pseudopolynomial time algorithm for subset sum. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1073-1084, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.69.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 3rd edition, 2009.
- Martin Dyer. Approximate counting by dynamic programming. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 693-699, 2003. URL: http://dx.doi.org/10.1145/780542.780643.
- Paweł Gawrychowski, Liran Markin, and Oren Weimann. A Faster FPTAS for #Knapsack. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP), pages 64:1-64:13, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.64.
- Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Štefankovic, Santosh Vempala, and Eric Vigoda. An FPTAS for #knapsack and related counting problems. In Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 817-826, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.32.
- 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.
- Konstantinos Koiliaris and Chao Xu. A faster pseudopolynomial time algorithm for subset sum. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1062-1072, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.68.
- Konstantinos Koiliaris and Chao Xu. Subset Sum Made Simple. CoRR, abs/1807.08248, 2018. URL: http://arxiv.org/abs/1807.08248.
- David Pisinger. Linear time algorithms for knapsack problems with bounded weights. Journal of Algorithms, 33(1):1-14, 1999. URL: http://dx.doi.org/10.1006/jagm.1999.1034.
- Romeo Rizzi and Alexandru I. Tomescu. Faster FPTASes for counting and random generation of knapsack solutions. In European Symposium on Algorithms (ESA), pages 762-773, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_63.