{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:29:58Z","timestamp":1763458198183,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T00:00:00Z","timestamp":1669852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100018960","name":"National Technical University of Athens","doi-asserted-by":"crossref","award":["Basic Research Programme, PEVE 2020","Basic Research Programme, PEVE 2020"],"award-info":[{"award-number":["Basic Research Programme, PEVE 2020","Basic Research Programme, PEVE 2020"]}],"id":[{"id":"10.13039\/501100018960","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,1]]},"abstract":"Abstract<\/jats:title>We present new, faster pseudopolynomial time algorithms for the k<\/jats:italic>-Subset Sum<\/jats:sc> problem, defined as follows: given a set Z<\/jats:italic> of n<\/jats:italic> positive integers and k<\/jats:italic> targets $$t_1, \\ldots , t_k$$<\/jats:tex-math>\n \n \n t<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n t<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, determine whether there exist k<\/jats:italic> disjoint subsets $$Z_1,\\dots ,Z_k \\subseteq Z$$<\/jats:tex-math>\n \n \n Z<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n \n Z<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n \u2286<\/mml:mo>\n Z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, such that $$\\Sigma (Z_i) = t_i$$<\/jats:tex-math>\n \n \u03a3<\/mml:mi>\n \n (<\/mml:mo>\n \n Z<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n t<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for $$i = 1, \\ldots , k$$<\/jats:tex-math>\n \n i<\/mml:mi>\n =<\/mml:mo>\n 1<\/mml:mn>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Assuming $$t = \\max \\{ t_1, \\ldots , t_k \\}$$<\/jats:tex-math>\n \n t<\/mml:mi>\n =<\/mml:mo>\n max<\/mml:mo>\n {<\/mml:mo>\n \n t<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n ,<\/mml:mo>\n \n t<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the maximum among the given targets, a standard dynamic programming approach based on Bellman\u2019s algorithm can solve the problem in $$O(n t^k)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n \n t<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. We build upon recent advances on Subset Sum<\/jats:sc> due to Koiliaris and Xu, as well as Bringmann, in order to provide faster algorithms for k<\/jats:italic>-Subset Sum<\/jats:sc>. We devise two algorithms: a deterministic one of time complexity $${\\tilde{O}}(n^{k \/ (k+1)} t^k)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n k<\/mml:mi>\n \/<\/mml:mo>\n (<\/mml:mo>\n k<\/mml:mi>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n \n t<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and a randomised one of $${\\tilde{O}}(n + t^k)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \n t<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> complexity. Additionally, we show how these algorithms can be modified in order to incorporate cardinality constraints enforced on the solution subsets. We further demonstrate how these algorithms can be used in order to cope with variations of k<\/jats:italic>-Subset Sum<\/jats:sc>, namely Subset Sum Ratio<\/jats:sc>, k<\/jats:italic>-Subset Sum Ratio<\/jats:sc> and Multiple Subset Sum<\/jats:sc>.<\/jats:p>","DOI":"10.1007\/s10878-022-00928-0","type":"journal-article","created":{"date-parts":[[2022,12,1]],"date-time":"2022-12-01T15:03:49Z","timestamp":1669907029000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Faster algorithms for k-subset sum and variations"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1368-6334","authenticated-orcid":false,"given":"Antonis","family":"Antonopoulos","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6220-3722","authenticated-orcid":false,"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7825-2839","authenticated-orcid":false,"given":"Stavros","family":"Petsalakis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6505-2977","authenticated-orcid":false,"given":"Manolis","family":"Vasilakis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,12,1]]},"reference":[{"issue":"1","key":"928_CR1","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/3450524","volume":"18","author":"A Abboud","year":"2022","unstructured":"Abboud A, Bringmann K, Hermelin D, Shabtay D (2022) Seth-based lower bounds for subset sum and bicriteria path. ACM Trans Algorithms 18(1):6. https:\/\/doi.org\/10.1145\/3450524","journal-title":"ACM Trans Algorithms"},{"doi-asserted-by":"publisher","unstructured":"Alonistiotis G, Antonopoulos A, Melissinos N, Pagourtzis A, Petsalakis S, Vasilakis M (2022) Approximating subset sum ratio via subset sum computations. In: Combinatorial algorithms\u201433rd international workshop, IWOCA 2022. Lecture Notes in computer science, vol 13270, pp 73\u201385. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-031-06678-8_6","key":"928_CR2","DOI":"10.1007\/978-3-031-06678-8_6"},{"doi-asserted-by":"publisher","unstructured":"Antonopoulos A, Pagourtzis A, Petsalakis S, Vasilakis M (2021) Faster algorithms for k-subset sum and variations. In: Frontiers of algorithmics, IJTCS-FAW 2021. Lecture notes in computer science, vol 12874, pp 37\u201352. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-97099-4_3","key":"928_CR3","DOI":"10.1007\/978-3-030-97099-4_3"},{"issue":"2","key":"928_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921670","volume":"7","author":"Y Aumann","year":"2011","unstructured":"Aumann Y, Lewenstein M, Lewenstein N, Tsur D (2011) Finding witnesses by peeling. ACM Trans Algorithms 7(2):1\u201315. https:\/\/doi.org\/10.1145\/1921659.1921670","journal-title":"ACM Trans Algorithms"},{"issue":"2","key":"928_CR5","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1006\/jcss.2001.1784","volume":"64","author":"C Bazgan","year":"2002","unstructured":"Bazgan C, Santha M, Tuza Z (2002) Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem. J Comput Syst Sci 64(2):160\u2013170. https:\/\/doi.org\/10.1006\/jcss.2001.1784","journal-title":"J Comput Syst Sci"},{"key":"928_CR6","volume-title":"Dynamic programming","author":"RE Bellman","year":"1957","unstructured":"Bellman RE (1957) Dynamic programming. Princeton University Press, Princeton"},{"doi-asserted-by":"publisher","unstructured":"Bringmann K (2017) A near-linear pseudopolynomial time algorithm for subset sum. In: Proceedings of the twenty-eighth annual ACM-SIAM symposium on discrete algorithms, SODA 2017, pp 1073\u20131084. SIAM, Philadelphia. https:\/\/doi.org\/10.1137\/1.9781611974782.69","key":"928_CR7","DOI":"10.1137\/1.9781611974782.69"},{"doi-asserted-by":"publisher","unstructured":"Bringmann K, Nakos V (2020) Top-k-convolution and the quest for near-linear output-sensitive subset sum. In: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC 2020, pp 982\u2013995. ACM, New York. https:\/\/doi.org\/10.1145\/3357713.3384308","key":"928_CR8","DOI":"10.1145\/3357713.3384308"},{"issue":"3\u20134","key":"928_CR9","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0020-0190(00)00010-7","volume":"73","author":"A Caprara","year":"2000","unstructured":"Caprara A, Kellerer H, Pferschy U (2000) A PTAS for the multiple subset sum problem with different knapsack capacities. Inf Process Lett 73(3\u20134):111\u2013118. https:\/\/doi.org\/10.1016\/S0020-0190(00)00010-7","journal-title":"Inf Process Lett"},{"issue":"2","key":"928_CR10","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1023\/A:1022584312032","volume":"9","author":"A Caprara","year":"2003","unstructured":"Caprara A, Kellerer H, Pferschy U (2003) A 3\/4-approximation algorithm for multiple subset sum. J Heuristics 9(2):99\u2013111. https:\/\/doi.org\/10.1023\/A:1022584312032","journal-title":"J Heuristics"},{"doi-asserted-by":"publisher","unstructured":"Cieliebak M, Eidenbenz SJ (2004) Measurement errors make the partial digest problem NP-hard. In: LATIN 2004: theoretical informatics, 6th Latin American symposium. Lecture notes in computer science, vol 2976, pp 379\u2013390. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-540-24698-5_42","key":"928_CR11","DOI":"10.1007\/978-3-540-24698-5_42"},{"doi-asserted-by":"publisher","unstructured":"Cieliebak M, Eidenbenz SJ, Pagourtzis A (2003a) Composing equipotent teams. In: Fundamentals of computation theory, 14th international symposium, FCT 2003. Lecture notes in computer science, vol 2751, pp 98\u2013108. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-540-45077-1_10","key":"928_CR12","DOI":"10.1007\/978-3-540-45077-1_10"},{"doi-asserted-by":"publisher","unstructured":"Cieliebak M, Eidenbenz SJ, Penna P (2003b) Noisy data make the partial digest problem NP-hard. In: Algorithms in bioinformatics, third international workshop, WABI 2003. Lecture notes in computer science, vol 2812, pp 111\u2013123. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-540-39763-2_9","key":"928_CR13","DOI":"10.1007\/978-3-540-39763-2_9"},{"issue":"3","key":"928_CR14","first-page":"151","volume":"14","author":"M Cieliebak","year":"2008","unstructured":"Cieliebak M, Eidenbenz SJ, Pagourtzis A, Schlude K (2008) On the complexity of variations of equal sum subsets. Nord J Comput 14(3):151\u2013172","journal-title":"Nord J Comput"},{"key":"928_CR15","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, London","edition":"3"},{"issue":"3","key":"928_CR16","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1016\/j.ejor.2018.10.043","volume":"274","author":"M Dell\u2019Amico","year":"2019","unstructured":"Dell\u2019Amico M, Delorme M, Iori M, Martello S (2019) Mathematical models and decomposition methods for the multiple Knapsack problem. Eur J Oper Res 274(3):886\u2013899. https:\/\/doi.org\/10.1016\/j.ejor.2018.10.043","journal-title":"Eur J Oper Res"},{"doi-asserted-by":"publisher","unstructured":"Jin C, Wu H (2018) A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In: 2nd Symposium on simplicity in algorithms (SOSA 2019), vol 69, pp 17. https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.17","key":"928_CR17","DOI":"10.4230\/OASIcs.SOSA.2019.17"},{"doi-asserted-by":"publisher","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. The IBM research symposia series, pp 85\u2013103. Springer, Boston. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","key":"928_CR18","DOI":"10.1007\/978-1-4684-2001-2_9"},{"doi-asserted-by":"publisher","unstructured":"Khan MA (2017) Some problems on graphs and arrangements of convex bodies. PRISM. https:\/\/doi.org\/10.11575\/PRISM\/10182","key":"928_CR19","DOI":"10.11575\/PRISM\/10182"},{"doi-asserted-by":"publisher","unstructured":"Koiliaris K, Xu C (2019) Faster pseudopolynomial time algorithms for subset sum. ACM Trans Algorithms 15(3):40. https:\/\/doi.org\/10.1145\/3329863","key":"928_CR20","DOI":"10.1145\/3329863"},{"unstructured":"Korf RE (2010) Objective functions for multi-way number partitioning. In: Proceedings of the third annual symposium on combinatorial search, SOCS 2010. Stone Mountain, Atlanta, July 8\u201310, 2010. AAAI Press","key":"928_CR21"},{"key":"928_CR22","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.cie.2019.01.010","volume":"129","author":"R Lahyani","year":"2019","unstructured":"Lahyani R, Chebil K, Khemakhem M, Coelho LC (2019) Matheuristics for solving the multiple knapsack problem with setup. Comput Ind Eng 129:76\u201389. https:\/\/doi.org\/10.1016\/j.cie.2019.01.010","journal-title":"Comput Ind Eng"},{"doi-asserted-by":"publisher","unstructured":"Lipton RJ, Markakis E, Mossel E, Saberi A (2004) On approximately fair allocations of indivisible goods. In: Proceedings of the 5th ACM conference on electronic commerce (EC-2004), pp 125\u2013131. ACM, New York. https:\/\/doi.org\/10.1145\/988772.988792","key":"928_CR23","DOI":"10.1145\/988772.988792"},{"doi-asserted-by":"publisher","unstructured":"Melissinos N, Pagourtzis A (2018) A faster FPTAS for the subset-sums ratio problem. In: Computing and combinatorics\u201424th international conference, COCOON 2018. Lecture notes in computer science, vol 10976, pp 602\u2013614. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-319-94776-1_50","key":"928_CR24","DOI":"10.1007\/978-3-319-94776-1_50"},{"doi-asserted-by":"publisher","unstructured":"Mucha M, Nederlof J, Pawlewicz J, Wegrzycki K (2019) Equal-subset-sum faster than the meet-in-the-middle. In: 27th Annual European symposium on algorithms, ESA. LIPIcs, vol 144, pp 73 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.73","key":"928_CR25","DOI":"10.4230\/LIPIcs.ESA.2019.73"},{"issue":"19\u201321","key":"928_CR26","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1016\/j.ipl.2013.07.009","volume":"113","author":"D Nanongkai","year":"2013","unstructured":"Nanongkai D (2013) Simple FPTAS for the subset-sums ratio problem. Inf Process Lett 113(19\u201321):750\u2013753. https:\/\/doi.org\/10.1016\/j.ipl.2013.07.009","journal-title":"Inf Process Lett"},{"issue":"3","key":"928_CR27","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou CH (1994) On the complexity of the parity argument and other inefficient proofs of existence. J Comput Syst Sci 48(3):498\u2013532. https:\/\/doi.org\/10.1016\/S0022-0000(05)80063-7","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"928_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1999.1034","volume":"33","author":"D Pisinger","year":"1999","unstructured":"Pisinger D (1999) Linear time algorithms for knapsack problems with bounded weights. J Algorithms 33(1):1\u201314. https:\/\/doi.org\/10.1006\/jagm.1999.1034","journal-title":"J Algorithms"},{"issue":"3","key":"928_CR29","doi-asserted-by":"publisher","first-page":"916","DOI":"10.1007\/s10878-018-0254-1","volume":"36","author":"D Recalde","year":"2018","unstructured":"Recalde D, Sever\u00edn D, Torres R, Vaca P (2018) An exact approach for the balanced k-way partitioning problem with weight constraints and its application to sports team realignment. J Comb Optim 36(3):916\u2013936. https:\/\/doi.org\/10.1007\/s10878-018-0254-1","journal-title":"J Comb Optim"},{"issue":"4","key":"928_CR30","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3184400","volume":"65","author":"EL Schreiber","year":"2018","unstructured":"Schreiber EL, Korf RE, Moffitt MD (2018) Optimal multi-way number partitioning. J ACM 65(4):24. https:\/\/doi.org\/10.1145\/3184400","journal-title":"J ACM"},{"issue":"1","key":"928_CR31","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/0221007","volume":"21","author":"L Tsai","year":"1992","unstructured":"Tsai L (1992) Asymptotic analysis of an algorithm for balanced parallel processor scheduling. SIAM J Comput 21(1):59\u201364. https:\/\/doi.org\/10.1137\/0221007","journal-title":"SIAM J Comput"},{"key":"928_CR32","doi-asserted-by":"publisher","first-page":"921","DOI":"10.12988\/ces.2017.79101","volume":"10","author":"N Voloch","year":"2017","unstructured":"Voloch N (2017) MSSP for 2-d sets with unknown parameters and a cryptographic application. Contemp Eng Sci 10:921\u2013931. https:\/\/doi.org\/10.12988\/ces.2017.79101","journal-title":"Contemp Eng Sci"},{"issue":"6","key":"928_CR33","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0020-0190(92)90226-L","volume":"42","author":"GJ Woeginger","year":"1992","unstructured":"Woeginger GJ, Yu Z (1992) On the equal-subset-sum problem. Inf Process Lett 42(6):299\u2013302. https:\/\/doi.org\/10.1016\/0020-0190(92)90226-L","journal-title":"Inf Process Lett"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00928-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00928-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00928-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:48:07Z","timestamp":1675496887000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00928-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["928"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00928-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,12,1]]},"assertion":[{"value":"26 October 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"24"}}