Approximating subset sum ratio via subset sum computations. (English) Zbl 07577691
Bazgan, Cristina (ed.) et al., Combinatorial algorithms. 33rd international workshop, IWOCA 2022, Trier, Germany, June 7–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13270, 73-85 (2022).
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 the closely related Subset Sum problem, hence any progress over those – such as the recent improvement due to Bringmann and Nakos [SODA 2021] – carries over to our FPTAS. 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 Subset Sum algorithm used. Furthermore, while the aforementioned state of the art complexity, expressed in the form \(\mathcal{O} ((n + 1 / \varepsilon )^c)\), has constant \(c = 5\), our results establish that \(c < 5\).
For the entire collection see [Zbl 1493.68006].
For the entire collection see [Zbl 1493.68006].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
| 68Wxx | Algorithms in computer science |
Keywords:
approximation scheme; combinatorial optimization; knapsack problems; subset sum; subset sum ratioSoftware:
KnapsackReferences:
| [1] | Abboud, A., Bringmann, K., Hermelin, D., Shabtay, D.: Seth-based lower bounds for subset sum and bicriteria path. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, 6-9 January 2019, pp. 41-57. SIAM (2019). doi:10.1137/1.9781611975482.3 · Zbl 1431.68040 |
| [2] | Antonopoulos, A., Pagourtzis, A., Petsalakis, S., Vasilakis, M.: Faster algorithms for \(k\)-subset sum and variations. In: J., Chen, Li, M., Zhang, G. (eds.): Frontiers of Algorithmics - International Joint Conference, IJTCS-FAW 2021, Beijing, 16-19 August 2021, Proceedings. LNCS, vol. 12874, pp. 37-52. Springer (2021). doi:10.1007/978-3-030-97099-4_3 · Zbl 1532.90091 |
| [3] | 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, 4-7 March 2015, Garching. LIPIcs, vol. 30, pp. 48-61. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015). doi:10.4230/LIPIcs.STACS.2015.48 · Zbl 1355.68109 |
| [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, 17-20 February 2016. doi:10.4230/LIPIcs.STACS.2016.13 · Zbl 1388.68079 |
| [5] | 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 |
| [6] | Bellman, RE, Dynamic Programming (1957), Princeton: Princeton University Press, Princeton · Zbl 0077.13605 |
| [7] | 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, Philadelphia (2017). doi:10.1137/1.9781611974782.69 · Zbl 1423.90210 |
| [8] | 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 (2020). doi:10.1145/3357713.3384308 · Zbl 07298304 |
| [9] | 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, Virtual Conference, 10-13 January 2021, pp. 1797-1815. SIAM (2021). doi:10.1137/1.9781611976465.108 · Zbl 07788446 |
| [10] | Cieliebak, M.; Eidenbenz, SJ, Measurement errors make the partial digest problem np-hard, LATIN 2004 Theoretical Informatics, 379-390 (2004), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 1196.68100 · doi:10.1007/978-3-540-24698-5_42 |
| [11] | Cieliebak, M.; Eidenbenz, SJ; Pagourtzis, A., Composing equipotent teams, Fundamentals of Computation Theory, 98-108 (2003), Berlin, Heidelberg: Springer, Berlin, Heidelberg · Zbl 1278.68104 · doi:10.1007/978-3-540-45077-1_10 |
| [12] | 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 |
| [13] | Cieliebak, M.; Eidenbenz, SJ; Penna, P., Noisy data make the partial digest problem NP-hard, Algorithms in Bioinformatics, Third International Workshop, WABI 2003, 111-123 (2003), Berlin, Heidelberg: Springer, Berlin, Heidelberg · doi:10.1007/978-3-540-39763-2_9 |
| [14] | Cygan, M., Mucha, M., Wegrzycki, K., Wlodarczyk, M.: On problems equivalent to (min, +)-convolution. ACM Trans. Algorithms 15(1), 14:1-14:25 (2019). doi:10.1145/3293465 · Zbl 1454.68052 |
| [15] | Dutta, P., Rajasree, M.S.: Efficient reductions and algorithms for variants of subset sum. CoRR abs/2112.11020 (2021). https://arxiv.org/abs/2112.11020 |
| [16] | 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 |
| [17] | Jin, C., Wu, H.: A simple near-linear pseudopolynomial time randomized algorithm for subset sum. In: 2nd Symposium on Simplicity in Algorithms (SOSA 2019), vol. 69, pp. 17:1-17:6 (2018). doi:10.4230/OASIcs.SOSA.2019.17 · Zbl 07902020 |
| [18] | Karp, RM, Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103 (1972), Boston: Springer, Boston · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [19] | 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 |
| [20] | Khan, M.A.: Some problems on graphs and arrangements of convex bodies (2017). doi:10.11575/PRISM/10182 |
| [21] | Koiliaris, K.; Xu, C., Faster pseudopolynomial time algorithms for subset sum, ACM Trans. Algorithms, 15, 3, 401-4020 (2019) · Zbl 1454.90076 · doi:10.1145/3329863 |
| [22] | 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 (2004). doi:10.1145/988772.988792 |
| [23] | Melissinos, N.; Pagourtzis, A., A faster FPTAS for the subset-sums ratio problem, Computing and Combinatorics - 24th International Conference, COCOON 2018, 602-614 (2018), Cham: Springer, Cham · Zbl 1509.68338 · doi:10.1007/978-3-319-94776-1_50 |
| [24] | Melissinos, N.; Pagourtzis, A.; Triommatis, T.; Li, M., Approximation schemes for subset sum ratio problems, Frontiers in Algorithmics, 96-107 (2020), Cham: Springer, Cham · Zbl 07370004 · doi:10.1007/978-3-030-59901-0_9 |
| [25] | 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:1-73:16 (2019). doi:10.4230/LIPIcs.ESA.2019.73 · Zbl 07525510 |
| [26] | 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, San Diego, California, 6-9 January 2019, pp. 70-88. SIAM (2019). doi:10.1137/1.9781611975482.5 · Zbl 1431.68155 |
| [27] | 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 |
| [28] | 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 |
| [29] | 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 |
| [30] | 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 |
| [31] | 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.
