Approximating subset sum ratio via partition computations. (English) Zbl 07850612
Summary: We present a new FPTAS for the Subset Sum Ratio 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 Partition, and clearly showcases the close relationship between the two algorithmic problems. Depending on the relationship between the size of the input set \(n\) and the error margin \(\varepsilon \), we improve upon the best currently known algorithm of Melissinos and Pagourtzis [COCOON 2018] of complexity \(\mathcal{O} (n^4 / \varepsilon )\). In particular, the exponent of \(n\) in our proposed scheme may decrease down to 2, depending on the Partition algorithm used.
MSC:
| 68Qxx | Theory of computing |
Software:
KnapsackReferences:
| [1] | Abboud, A.; Bringmann, K.; Hermelin, D.; Shabtay, D., Seth-based lower bounds for subset sum and bicriteria path, ACM Trans. Algorithms, 18, 1, 6-1622, 2022 · Zbl 07758400 · doi:10.1145/3450524 |
| [2] | 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-85. Springer, Cham (2022). doi:10.1007/978-3-031-06678-8_6 · Zbl 07577691 |
| [3] | Antonopoulos, A.; Pagourtzis, A.; Petsalakis, S.; Vasilakis, M., Faster algorithms for k-subset sum and variations, J. Comb. Optim., 45, 1, 24, 2023 · Zbl 1508.90075 · doi:10.1007/s10878-022-00928-0 |
| [4] | 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-11314. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2016). doi:10.4230/LIPIcs.STACS.2016.13 · Zbl 1388.68079 |
| [5] | 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-61. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2015). doi:10.4230/LIPIcs.STACS.2015.48 · Zbl 1355.68109 |
| [6] | Bazgan, C.; Santha, M.; Tuza, Z., Efficient approximation algorithms for the SUBSET-SUMS EQUALITY problem, J. Comput. Syst. Sci., 64, 2, 160-170, 2002 · Zbl 1078.90037 · doi:10.1006/jcss.2001.1784 |
| [7] | Bellman, RE, Dynamic Programming, 1957, Princeton: Princeton University Press, Princeton · Zbl 0077.13605 |
| [8] | 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-1815. SIAM, USA (2021). doi:10.1137/1.9781611976465.108 · Zbl 07788446 |
| [9] | 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-995. ACM, New York, NY, USA (2020). doi:10.1145/3357713.3384308 · Zbl 07298304 |
| [10] | 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-1084. SIAM, USA (2017). doi:10.1137/1.9781611974782.69 · Zbl 1423.90210 |
| [11] | 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-108. Springer, Berlin, Heidelberg (2003). doi:10.1007/978-3-540-45077-1_10 · Zbl 1278.68104 |
| [12] | 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-123. Springer, Berlin, Heidelberg (2003). doi:10.1007/978-3-540-39763-2_9 |
| [13] | 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-390. Springer, Berlin, Heidelberg (2004). doi:10.1007/978-3-540-24698-5_42 · Zbl 1196.68100 |
| [14] | Cieliebak, M.; Eidenbenz, SJ; Pagourtzis, A.; Schlude, K., On the complexity of variations of equal sum subsets, Nord. J. Comput., 14, 3, 151-172, 2008 · Zbl 1187.68248 |
| [15] | Cygan, M.; Mucha, M.; Wegrzycki, K.; Wlodarczyk, M., On problems equivalent to (min, +)-convolution, ACM Trans. Algorithms, 15, 1, 14-11425, 2019 · Zbl 1454.68052 · doi:10.1145/3293465 |
| [16] | 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-2979. SIAM, USA (2023). doi:10.1137/1.9781611977554.ch113 · Zbl 07848073 |
| [17] | 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-251. Springer, Cham (2022). doi:10.1007/978-3-030-95018-7_19 · Zbl 07683176 |
| [18] | Horowitz, E.; Sahni, S., Computing partitions with applications to the knapsack problem, J. ACM, 21, 2, 277-292, 1974 · Zbl 0329.90046 · doi:10.1145/321812.321823 |
| [19] | 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-1176. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2019). doi:10.4230/OASIcs.SOSA.2019.17 · Zbl 07902020 |
| [20] | 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-103. Springer, Boston, MA (1972). doi:10.1007/978-1-4684-2001-2_9 · Zbl 1467.68065 |
| [21] | Kellerer, H.; Mansini, R.; Pferschy, U.; Speranza, MG, An efficient fully polynomial approximation scheme for the subset-sum problem, J. Comput. Syst. Sci., 66, 2, 349-370, 2003 · Zbl 1045.68157 · doi:10.1016/S0022-0000(03)00006-0 |
| [22] | Khan, MA, Some problems on graphs and arrangements of convex bodies, PRISM, 2017 · doi:10.11575/PRISM/10182 |
| [23] | Koiliaris, K.; Xu, C., Faster pseudopolynomial time algorithms for subset sum, ACM Trans. Algorithms, 15, 3, 40-14020, 2019 · Zbl 1454.90076 · doi:10.1145/3329863 |
| [24] | 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-131. ACM, New York, NY, USA (2004). doi:10.1145/988772.988792 |
| [25] | Melissinos, N., Pagourtzis, A.: A faster FPTAS for the subset-sums ratio problem. In: Computing and Combinatorics—24th International Conference, COCOON 2018. Lecture Notes in Computer Science, vol. 10976, pp. 602-614. Springer, Cham (2018). doi:10.1007/978-3-319-94776-1_50 · Zbl 1509.68338 |
| [26] | Melissinos, N.; Pagourtzis, A.; Triommatis, T., Approximation schemes for subset-sums ratio problems, Theor. Comput. Sci., 931, 17-30, 2022 · Zbl 1535.68486 · doi:10.1016/j.tcs.2022.07.027 |
| [27] | 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-17316 (2019). doi:10.4230/LIPIcs.ESA.2019.73 · Zbl 07525510 |
| [28] | 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-88. SIAM, USA (2019). doi:10.1137/1.9781611975482.5 · Zbl 1431.68155 |
| [29] | Nanongkai, D., Simple FPTAS for the subset-sums ratio problem, Inf. Process. Lett., 113, 19-21, 750-753, 2013 · Zbl 1284.68674 · doi:10.1016/j.ipl.2013.07.009 |
| [30] | Papadimitriou, CH, On the complexity of the parity argument and other inefficient proofs of existence, J. Comput. Syst. Sci., 48, 3, 498-532, 1994 · Zbl 0806.68048 · doi:10.1016/S0022-0000(05)80063-7 |
| [31] | Pisinger, D., Linear time algorithms for knapsack problems with bounded weights, J. Algorithms, 33, 1, 1-14, 1999 · Zbl 0951.90047 · doi:10.1006/jagm.1999.1034 |
| [32] | Voloch, N., Mssp for 2-d sets with unknown parameters and a cryptographic application, Contemp. Eng. Sci., 10, 921-931, 2017 · doi:10.12988/ces.2017.79101 |
| [33] | Woeginger, GJ; Yu, Z., On the equal-subset-sum problem, Inf. Process. Lett., 42, 6, 299-302, 1992 · Zbl 0772.68059 · doi:10.1016/0020-0190(92)90226-L |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
