Document Open Access Logo

A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum

Authors Ce Jin, Hongxun Wu

PDF

File

Thumbnail PDF
PDF
OASIcs.SOSA.2019.17.pdf
  • Filesize: 409 kB
  • 6 pages

Document Identifiers

Subject Classification

Keywords
  • subset sum
  • formal power series
  • FFT

Metrics

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.

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

Author Details

Ce Jin
Hongxun Wu

References

  1. 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.
  2. Richard E. Bellman. Dynamic programming. Princeton University Press, 1957. Google Scholar
  3. 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.
  4. 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.
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 3rd edition, 2009. Google Scholar
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. Konstantinos Koiliaris and Chao Xu. Subset Sum Made Simple. CoRR, abs/1807.08248, 2018. URL: http://arxiv.org/abs/1807.08248.
  12. 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.
  13. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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