{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T00:01:51Z","timestamp":1773187311520,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,12]],"date-time":"2019-06-12T00:00:00Z","timestamp":1560297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            Given a (multi) set\n            <jats:italic>S<\/jats:italic>\n            of\n            <jats:italic>n<\/jats:italic>\n            positive integers and a target integer\n            <jats:italic>u<\/jats:italic>\n            , the subset sum problem is to decide if there is a subset of\n            <jats:italic>S<\/jats:italic>\n            that sums up to\n            <jats:italic>u<\/jats:italic>\n            . We present a series of new algorithms that compute and return\n            <jats:italic>all<\/jats:italic>\n            the realizable subset sums up to the integer\n            <jats:italic>u<\/jats:italic>\n            in \u00d5(min { \u221a\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>u<\/jats:italic>\n            ,\n            <jats:italic>u<\/jats:italic>\n            <jats:sup>5\/4<\/jats:sup>\n            ,\u03c3 }), where \u03c3 is the sum of all elements of\n            <jats:italic>S<\/jats:italic>\n            and \u00d5 hides polylogarithmic factors. We also present a modified algorithm for integers modulo\n            <jats:italic>m<\/jats:italic>\n            , which computes all the realizable subset sums modulo\n            <jats:italic>m<\/jats:italic>\n            in \u00d5(min { \u221a\n            <jats:italic>n<\/jats:italic>\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>m<\/jats:italic>\n            <jats:sup>5\/4<\/jats:sup>\n            }) time.\n          <\/jats:p>\n          <jats:p>\n            Our contributions improve upon the standard dynamic programming algorithm that runs in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>nu<\/jats:italic>\n            ) time. To the best of our knowledge, the new algorithms are the fastest deterministic algorithms for this problem. The new results can be employed in various algorithmic problems, from graph bipartition to computational social choice. Finally, we also improve a result on covering Z\n            <jats:sub>\n              <jats:italic>m<\/jats:italic>\n            <\/jats:sub>\n            , which might be of independent interest.\n          <\/jats:p>","DOI":"10.1145\/3329863","type":"journal-article","created":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T12:09:28Z","timestamp":1560427768000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Faster Pseudopolynomial Time Algorithms for Subset Sum"],"prefix":"10.1145","volume":"15","author":[{"given":"Konstantinos","family":"Koiliaris","sequence":"first","affiliation":[{"name":"University of Illinois, Urbana-Champaign, IL, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4417-3299","authenticated-orcid":false,"given":"Chao","family":"Xu","sequence":"additional","affiliation":[{"name":"Yahoo! Research, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(87)90061-8"},{"key":"e_1_2_1_3_1","article-title":"Finding witnesses by peeling","volume":"7","author":"Aumann Yonatan","year":"2011","unstructured":"Yonatan Aumann , Moshe Lewenstein , Noa Lewenstein , and Dekel Tsur . 2011 . Finding witnesses by peeling . ACM Trans. Alg. 7 , 2, Article 24 (Mar. 2011), 15 pages. Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, and Dekel Tsur. 2011. Finding witnesses by peeling. ACM Trans. Alg. 7, 2, Article 24 (Mar. 2011), 15 pages.","journal-title":"ACM Trans. Alg."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030107"},{"key":"e_1_2_1_6_1","volume-title":"Fast Algorithms for Digital Signal Processing","author":"Blahut Richard E.","unstructured":"Richard E. Blahut . 1985. Fast Algorithms for Digital Signal Processing ( 1 st ed.). Addison-Wesley Longman Publishing Co., Inc. , Boston, MA . Richard E. Blahut. 1985. Fast Algorithms for Digital Signal Processing (1st ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA.","edition":"1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20346"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.69"},{"key":"e_1_2_1_9_1","volume-title":"Siu Man Chan, and Siu On Chan","author":"Cai Leizhen","year":"2006","unstructured":"Leizhen Cai , Siu Man Chan, and Siu On Chan . 2006 . Random Separation : A New Method for Solving Fixed-Cardinality Optimization Problems. Springer Berlin Heidelberg , 239--250. Leizhen Cai, Siu Man Chan, and Siu On Chan. 2006. Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. Springer Berlin Heidelberg, 239--250."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1379085.1379088"},{"key":"e_1_2_1_11_1","first-page":"363","article-title":"New algorithm for dense subset-sum problem","volume":"258","author":"Chaimovich Mark","year":"1999","unstructured":"Mark Chaimovich . 1999 . New algorithm for dense subset-sum problem . Ast\u00e9risque 258 (1999), 363 -- 373 . Mark Chaimovich. 1999. New algorithm for dense subset-sum problem. Ast\u00e9risque 258 (1999), 363--373.","journal-title":"Ast\u00e9risque"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2338078"},{"key":"e_1_2_1_13_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald Rivest , and Clifford Stein . 2014. Introduction to Algorithms ( 3 rd ed.). The MIT Press , Cambridge, MA . Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein. 2014. Introduction to Algorithms (3rd ed.). The MIT Press, Cambridge, MA.","edition":"3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.5.2.266"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 16th International Conference on Extending Database Technology (EDBT\u201913)","author":"Dautrich Jonathan L.","unstructured":"Jonathan L. Dautrich , Jr. and Chinya V. Ravishankar . 2013. Compromising privacy in precise query protocols . In Proceedings of the 16th International Conference on Extending Database Technology (EDBT\u201913) . ACM, 155--166. Jonathan L. Dautrich, Jr. and Chinya V. Ravishankar. 2013. Compromising privacy in precise query protocols. In Proceedings of the 16th International Conference on Extending Database Technology (EDBT\u201913). ACM, 155--166."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1540666.1541109"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0841"},{"key":"e_1_2_1_18_1","first-page":"41","article-title":"Theorem in the additive number theory","volume":"10","author":"Erd\u00f6s Paul","year":"1961","unstructured":"Paul Erd\u00f6s , Abraham Ginzburg , and Abraham Ziv . 1961 . Theorem in the additive number theory . Bull. Res. Council Israel, Sect. F. 10 (1961), 41 -- 43 . Paul Erd\u00f6s, Abraham Ginzburg, and Abraham Ziv. 1961. Theorem in the additive number theory. Bull. Res. Council Israel, Sect. F. 10 (1961), 41--43.","journal-title":"Bull. Res. Council Israel, Sect. F."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.1.332"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC\u201990)","author":"Fredman M. L.","unstructured":"M. L. Fredman and D. E. Willard . 1990. BLASTING through the information theoretic barrier with FUSION TREES . In Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC\u201990) . ACM, 1--7. M. L. Fredman and D. E. Willard. 1990. BLASTING through the information theoretic barrier with FUSION TREES. In Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC\u201990). ACM, 1--7."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220072"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Zvi Galil and Oded Margalit. 1991. An almost linear-time algorithm for the dense subset-sum problem. In Automata Languages and Programming Javier Leach Albert Burkhard Monien and Mario Rodr\u00edguez Artalejo (Eds.). Springer Berlin Heidelberg 719--727.   Zvi Galil and Oded Margalit. 1991. An almost linear-time algorithm for the dense subset-sum problem. In Automata Languages and Programming Javier Leach Albert Burkhard Monien and Mario Rodr\u00edguez Artalejo (Eds.). Springer Berlin Heidelberg 719--727.","DOI":"10.1007\/3-540-54233-7_177"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.20202"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930613891"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the Conference on Innovations in Computer Science. 321--337","author":"Guruswami Venkatesan","year":"2011","unstructured":"Venkatesan Guruswami , Yury Makarychev , Prasad Raghavendra , David Steurer , and Yuan Zhou . 2011 . Finding almost-perfect graph bisections . In Proceedings of the Conference on Innovations in Computer Science. 321--337 . Retrieved from: http:\/\/conference.itcs.tsinghua.edu.cn\/ICS 2011\/content\/papers\/11.html. Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, and Yuan Zhou. 2011. Finding almost-perfect graph bisections. In Proceedings of the Conference on Innovations in Computer Science. 321--337. Retrieved from: http:\/\/conference.itcs.tsinghua.edu.cn\/ICS2011\/content\/papers\/11.html."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2007.12.007"},{"key":"e_1_2_1_27_1","volume-title":"An Introduction to the Theory of Numbers","author":"Hardy Godfrey Harold","unstructured":"Godfrey Harold Hardy and Edward Maitland Wright . 1979. An Introduction to the Theory of Numbers ( 5 th ed.). Clarendon Press , Oxford . Retrieved from: http:\/\/opac.inria.fr\/record&equals;b1099316. Godfrey Harold Hardy and Edward Maitland Wright. 1979. An Introduction to the Theory of Numbers (5th ed.). Clarendon Press, Oxford. Retrieved from: http:\/\/opac.inria.fr\/record&equals;b1099316.","edition":"5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199612)28:4<221::AID-NET6>3.0.CO;2-N"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA\u201919)","volume":"69","author":"Jin Ce","year":"2018","unstructured":"Ce Jin and Hongxun Wu . 2018 . A simple near-linear pseudopolynomial time randomized algorithm for subset sum . In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA\u201919) , (OpenAccess Series in Informatics (OASIcs)), Jeremy T. Fineman and Michael Mitzenmacher (Eds.) , Vol. 69 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 17:1--17:6. Ce Jin and Hongxun Wu. 2018. A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA\u201919), (OpenAccess Series in Informatics (OASIcs)), Jeremy T. Fineman and Michael Mitzenmacher (Eds.), Vol. 69. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 17:1--17:6."},{"key":"e_1_2_1_32_1","volume-title":"Complexity of Computer Computations, Raymond E","author":"Karp Richard M.","unstructured":"Richard M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations, Raymond E . Miller, James W. Thatcher, and Jean D. Bohlinger (Eds.). Springer US , 85--103. Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger (Eds.). Springer US, 85--103."},{"key":"e_1_2_1_33_1","volume-title":"Knapsack Problems","author":"Kellerer Hans","unstructured":"Hans Kellerer , Ulrich Pferschy , and David Pisinger . 2004. Knapsack Problems . Springer . Hans Kellerer, Ulrich Pferschy, and David Pisinger. 2004. Knapsack Problems. Springer."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199905)33:3<189::AID-NET5>3.0.CO;2-2"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.68"},{"key":"e_1_2_1_36_1","volume-title":"Subset sum made simple. CoRR abs\/1807.08248","author":"Koiliaris Konstantinos","year":"2018","unstructured":"Konstantinos Koiliaris and Chao Xu. 2018. Subset sum made simple. CoRR abs\/1807.08248 ( 2018 ). Retrieved from: http:\/\/arxiv.org\/abs\/1807.08248. Konstantinos Koiliaris and Chao Xu. 2018. Subset sum made simple. CoRR abs\/1807.08248 (2018). Retrieved from: http:\/\/arxiv.org\/abs\/1807.08248."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.339"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.5"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80027-4"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-28-2-147-156"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070050042"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1034"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0989-y"},{"key":"e_1_2_1_45_1","first-page":"1","article-title":"Coordinated logistics scheduling for in-house production and outsourcing","volume":"5","author":"Qi Xiangtong","year":"2008","unstructured":"Xiangtong Qi . 2008 . Coordinated logistics scheduling for in-house production and outsourcing . IEEE Trans. Auto. Sci. Eng. 5 , 1 (Jan. 2008), 188--192. Xiangtong Qi. 2008. Coordinated logistics scheduling for in-house production and outsourcing. IEEE Trans. Auto. Sci. Eng. 5, 1 (Jan. 2008), 188--192.","journal-title":"IEEE Trans. Auto. Sci. Eng."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-42-4-367-389"},{"key":"e_1_2_1_47_1","volume-title":"Asymptotically Fast Algorithms for the Numerical Muitiplication and Division of Polynomials with Complex Coefficients","author":"Sch\u00f6nhage Arnold","unstructured":"Arnold Sch\u00f6nhage . 1982. Asymptotically Fast Algorithms for the Numerical Muitiplication and Division of Polynomials with Complex Coefficients . Springer Berlin Heidelberg , 3--15. Arnold Sch\u00f6nhage. 1982. Asymptotically Fast Algorithms for the Numerical Muitiplication and Division of Polynomials with Complex Coefficients. Springer Berlin Heidelberg, 3--15."},{"key":"e_1_2_1_48_1","volume-title":"The probabilistic convolution tree: Efficient exact Bayesian inference for faster LC-MS\/MS protein inference. PLoS ONE 9, 3 (03","author":"Serang Oliver","year":"2014","unstructured":"Oliver Serang . 2014. The probabilistic convolution tree: Efficient exact Bayesian inference for faster LC-MS\/MS protein inference. PLoS ONE 9, 3 (03 2014 ), e91507. Oliver Serang. 2014. The probabilistic convolution tree: Efficient exact Bayesian inference for faster LC-MS\/MS protein inference. PLoS ONE 9, 3 (03 2014), e91507."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2015.0013"},{"key":"e_1_2_1_50_1","first-page":"1","article-title":"On \u0394(x, n) &equals; &phis;(x, n)&minus; x &phis;(n)\/n","volume":"44","author":"Suryanarayana D.","year":"1974","unstructured":"D. Suryanarayana . 1974 . On \u0394(x, n) &equals; &phis;(x, n)&minus; x &phis;(n)\/n . Proc. Amer. Math. Soc. 44 , 1 (Jan. 1974), 17--21. D. Suryanarayana. 1974. On \u0394(x, n) &equals; &phis;(x, n)&minus; x &phis;(n)\/n. Proc. Amer. Math. Soc. 44, 1 (Jan. 1974), 17--21.","journal-title":"Proc. Amer. Math. Soc."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-016-9326-8"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-17-3-227-229"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063791"},{"key":"e_1_2_1_54_1","series-title":"Lecture Notes in Computer Science","volume-title":"Efficient computation of power indices for weighted majority games","author":"Uno Takeaki","unstructured":"Takeaki Uno . 2012. Efficient computation of power indices for weighted majority games . In Algorithms and Computation, Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee (Eds.). Lecture Notes in Computer Science , Vol. 7676 . Springer Berlin Heidelberg , 679--689. Takeaki Uno. 2012. Efficient computation of power indices for weighted majority games. In Algorithms and Computation, Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee (Eds.). Lecture Notes in Computer Science, Vol. 7676. Springer Berlin Heidelberg, 679--689."},{"key":"e_1_2_1_55_1","volume-title":"A Structural Approach to Subset-Sum Problems","author":"Van Vu.","unstructured":"Van Vu. 2008. A Structural Approach to Subset-Sum Problems . Springer Berlin Heidelberg , 525--545. Van Vu. 2008. A Structural Approach to Subset-Sum Problems. Springer Berlin Heidelberg, 525--545."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329863","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3329863","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:26:23Z","timestamp":1750206383000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3329863"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,12]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3329863"],"URL":"https:\/\/doi.org\/10.1145\/3329863","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,12]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}