{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T16:28:44Z","timestamp":1747153724105,"version":"3.40.5"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:00:00Z","timestamp":1705017600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:00:00Z","timestamp":1705017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a new FPTAS for the <jats:sc>Subset Sum Ratio<\/jats:sc> problem, which, given a set of integers, asks for two disjoint subsets such that the ratio of their sums is as close to 1 as possible. Our scheme makes use of exact and approximate algorithms for <jats:sc>Partition<\/jats:sc>, and clearly showcases the close relationship between the two algorithmic problems. Depending on the relationship between the size of the input set <jats:italic>n<\/jats:italic> and the error margin <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varepsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03b5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O} (n^4 \/ \\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>4<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In particular, the exponent of <jats:italic>n<\/jats:italic> in our proposed scheme may decrease down to 2, depending on the <jats:sc>Partition<\/jats:sc> algorithm used.<\/jats:p>","DOI":"10.1007\/s00236-023-00451-7","type":"journal-article","created":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T14:02:17Z","timestamp":1705068137000},"page":"101-113","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating subset sum ratio via partition computations"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1277-5017","authenticated-orcid":false,"given":"Giannis","family":"Alonistiotis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1368-6334","authenticated-orcid":false,"given":"Antonis","family":"Antonopoulos","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0864-9803","authenticated-orcid":false,"given":"Nikolaos","family":"Melissinos","sequence":"additional","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":[[2024,1,12]]},"reference":[{"issue":"1","key":"451_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.: Seth-based lower bounds for subset sum and bicriteria path. ACM Trans. Algorithms 18(1), 6\u20131622 (2022). https:\/\/doi.org\/10.1145\/3450524","journal-title":"ACM Trans. Algorithms"},{"key":"451_CR2","doi-asserted-by":"publisher","unstructured":"Alonistiotis, G., Antonopoulos, A., Melissinos, N., Pagourtzis, A., Petsalakis, S., Vasilakis, M.: Approximating subset sum ratio via subset sum computations. In: Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022. Lecture Notes in Computer Science, vol. 13270, pp. 73\u201385. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-06678-8_6","DOI":"10.1007\/978-3-031-06678-8_6"},{"issue":"1","key":"451_CR3","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/s10878-022-00928-0","volume":"45","author":"A Antonopoulos","year":"2023","unstructured":"Antonopoulos, A., Pagourtzis, A., Petsalakis, S., Vasilakis, M.: Faster algorithms for k-subset sum and variations. J. Comb. Optim. 45(1), 24 (2023). https:\/\/doi.org\/10.1007\/s10878-022-00928-0","journal-title":"J. Comb. Optim."},{"key":"451_CR4","doi-asserted-by":"publisher","unstructured":"Austrin, P., Kaski, P., Koivisto, M., Nederlof, J.: Dense subset sum may be the hardest. In: 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016. LIPIcs, vol. 47, pp. 13\u201311314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2016.13","DOI":"10.4230\/LIPIcs.STACS.2016.13"},{"key":"451_CR5","doi-asserted-by":"publisher","unstructured":"Austrin, P., Kaski, P., Koivisto, M., Nederlof, J.: Subset sum in the absence of concentration. In: 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015. LIPIcs, vol. 30, pp. 48\u201361. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.48","DOI":"10.4230\/LIPIcs.STACS.2015.48"},{"issue":"2","key":"451_CR6","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.: Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem. J. Comput. Syst. Sci. 64(2), 160\u2013170 (2002). https:\/\/doi.org\/10.1006\/jcss.2001.1784","journal-title":"J. Comput. Syst. Sci."},{"key":"451_CR7","volume-title":"Dynamic Programming","author":"RE Bellman","year":"1957","unstructured":"Bellman, R.E.: Dynamic Programming. Princeton University Press, Princeton (1957)"},{"key":"451_CR8","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Nakos, V.: A fine-grained perspective on approximating subset sum and partition. In: Proceedings of the 2021 ACM-SIAM symposium on discrete algorithms, SODA 2021, pp. 1797\u20131815. SIAM, USA (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.108","DOI":"10.1137\/1.9781611976465.108"},{"key":"451_CR9","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Nakos, V.: Top-k-convolution and the quest for near-linear output-sensitive subset sum. In: Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 982\u2013995. ACM, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3357713.3384308","DOI":"10.1145\/3357713.3384308"},{"key":"451_CR10","doi-asserted-by":"publisher","unstructured":"Bringmann, K.: 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, USA (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.69","DOI":"10.1137\/1.9781611974782.69"},{"key":"451_CR11","doi-asserted-by":"publisher","unstructured":"Cieliebak, M., Eidenbenz, S.J., Pagourtzis, A.: 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, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45077-1_10","DOI":"10.1007\/978-3-540-45077-1_10"},{"key":"451_CR12","doi-asserted-by":"publisher","unstructured":"Cieliebak, M., Eidenbenz, S.J., Penna, P.: 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, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39763-2_9","DOI":"10.1007\/978-3-540-39763-2_9"},{"key":"451_CR13","doi-asserted-by":"publisher","unstructured":"Cieliebak, M., Eidenbenz, S.J.: 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, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_42","DOI":"10.1007\/978-3-540-24698-5_42"},{"issue":"3","key":"451_CR14","first-page":"151","volume":"14","author":"M Cieliebak","year":"2008","unstructured":"Cieliebak, M., Eidenbenz, S.J., Pagourtzis, A., Schlude, K.: On the complexity of variations of equal sum subsets. Nord. J. Comput. 14(3), 151\u2013172 (2008)","journal-title":"Nord. J. Comput."},{"issue":"1","key":"451_CR15","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/3293465","volume":"15","author":"M Cygan","year":"2019","unstructured":"Cygan, M., Mucha, M., Wegrzycki, K., Wlodarczyk, M.: On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms 15(1), 14\u201311425 (2019). https:\/\/doi.org\/10.1145\/3293465","journal-title":"ACM Trans. Algorithms"},{"key":"451_CR16","doi-asserted-by":"publisher","unstructured":"Deng, M., Jin, C., Mao, X.: Approximating knapsack and partition via dense subset sums. In: Proceedings of the 2023 ACM-SIAM symposium on discrete algorithms, SODA 2023, pp. 2961\u20132979. SIAM, USA (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch113","DOI":"10.1137\/1.9781611977554.ch113"},{"key":"451_CR17","doi-asserted-by":"publisher","unstructured":"Dutta, P., Rajasree, M.S.: Algebraic algorithms for variants of subset sum. In: Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022. Lecture Notes in Computer Science, vol. 13179, pp. 237\u2013251. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-95018-7_19","DOI":"10.1007\/978-3-030-95018-7_19"},{"issue":"2","key":"451_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM 21(2), 277\u2013292 (1974). https:\/\/doi.org\/10.1145\/321812.321823","journal-title":"J. ACM"},{"key":"451_CR19","doi-asserted-by":"publisher","unstructured":"Jin, C., Wu, H.: A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In: 2nd symposium on simplicity in algorithms, SOSA 2019. OASIcs, vol. 69, pp. 17\u20131176. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019). https:\/\/doi.org\/10.4230\/OASIcs.SOSA.2019.17","DOI":"10.4230\/OASIcs.SOSA.2019.17"},{"key":"451_CR20","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a symposium on the complexity of computer computations. The IBM Research Symposia Series, pp. 85\u2013103. Springer, Boston, MA (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"2","key":"451_CR21","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/S0022-0000(03)00006-0","volume":"66","author":"H Kellerer","year":"2003","unstructured":"Kellerer, H., Mansini, R., Pferschy, U., Speranza, M.G.: An efficient fully polynomial approximation scheme for the subset-sum problem. J. Comput. Syst. Sci. 66(2), 349\u2013370 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00006-0","journal-title":"J. Comput. Syst. Sci."},{"key":"451_CR22","doi-asserted-by":"publisher","DOI":"10.11575\/PRISM\/10182","author":"MA Khan","year":"2017","unstructured":"Khan, M.A.: Some problems on graphs and arrangements of convex bodies. PRISM (2017). https:\/\/doi.org\/10.11575\/PRISM\/10182","journal-title":"PRISM"},{"issue":"3","key":"451_CR23","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/3329863","volume":"15","author":"K Koiliaris","year":"2019","unstructured":"Koiliaris, K., Xu, C.: Faster pseudopolynomial time algorithms for subset sum. ACM Trans. Algorithms 15(3), 40\u201314020 (2019). https:\/\/doi.org\/10.1145\/3329863","journal-title":"ACM Trans. Algorithms"},{"key":"451_CR24","doi-asserted-by":"publisher","unstructured":"Lipton, R.J., Markakis, E., Mossel, E., Saberi, A.: 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, NY, USA (2004). https:\/\/doi.org\/10.1145\/988772.988792","DOI":"10.1145\/988772.988792"},{"key":"451_CR25","doi-asserted-by":"publisher","unstructured":"Melissinos, N., Pagourtzis, A.: 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 (2018). https:\/\/doi.org\/10.1007\/978-3-319-94776-1_50","DOI":"10.1007\/978-3-319-94776-1_50"},{"key":"451_CR26","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.tcs.2022.07.027","volume":"931","author":"N Melissinos","year":"2022","unstructured":"Melissinos, N., Pagourtzis, A., Triommatis, T.: Approximation schemes for subset-sums ratio problems. Theor. Comput. Sci. 931, 17\u201330 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.07.027","journal-title":"Theor. Comput. Sci."},{"key":"451_CR27","doi-asserted-by":"publisher","unstructured":"Mucha, M., Nederlof, J., Pawlewicz, J., Wegrzycki, K.: Equal-subset-sum faster than the meet-in-the-middle. In: 27th annual european symposium on algorithms, ESA 2019. LIPIcs, vol. 144, pp. 73\u201317316 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.73","DOI":"10.4230\/LIPIcs.ESA.2019.73"},{"key":"451_CR28","doi-asserted-by":"publisher","unstructured":"Mucha, M., Wegrzycki, K., Wlodarczyk, M.: A subquadratic approximation scheme for partition. In: Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms, SODA 2019, pp. 70\u201388. SIAM, USA (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.5","DOI":"10.1137\/1.9781611975482.5"},{"issue":"19\u201321","key":"451_CR29","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.: Simple FPTAS for the subset-sums ratio problem. Inf. Process. Lett. 113(19\u201321), 750\u2013753 (2013). https:\/\/doi.org\/10.1016\/j.ipl.2013.07.009","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"451_CR30","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80063-7","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"451_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1999.1034","volume":"33","author":"D Pisinger","year":"1999","unstructured":"Pisinger, D.: Linear time algorithms for knapsack problems with bounded weights. J. Algorithms 33(1), 1\u201314 (1999). https:\/\/doi.org\/10.1006\/jagm.1999.1034","journal-title":"J. Algorithms"},{"key":"451_CR32","doi-asserted-by":"publisher","first-page":"921","DOI":"10.12988\/ces.2017.79101","volume":"10","author":"N Voloch","year":"2017","unstructured":"Voloch, N.: Mssp for 2-d sets with unknown parameters and a cryptographic application. Contemp. Eng. Sci. 10, 921\u2013931 (2017). https:\/\/doi.org\/10.12988\/ces.2017.79101","journal-title":"Contemp. Eng. Sci."},{"issue":"6","key":"451_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, G.J., Yu, Z.: On the equal-subset-sum problem. Inf. Process. Lett. 42(6), 299\u2013302 (1992). https:\/\/doi.org\/10.1016\/0020-0190(92)90226-L","journal-title":"Inf. Process. Lett."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-023-00451-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-023-00451-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-023-00451-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T10:04:51Z","timestamp":1715681091000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-023-00451-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,12]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["451"],"URL":"https:\/\/doi.org\/10.1007\/s00236-023-00451-7","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2024,1,12]]},"assertion":[{"value":"6 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 December 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2024","order":3,"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"}}]}}