×
Melissinos, Nikolaos; Pagourtzis, Aris; Triommatis, Theofilos

Approximation schemes for subset-sums ratio problems. (English) Zbl 1535.68486

Theor. Comput. Sci. 931, 17-30 (2022).
Summary: We consider the Subset-Sums Ratio Problem (SSR), in which given a set of integers the goal is to find two subsets such that the ratio of their sums is as close to 1 as possible, and we introduce a family of variations of SSR that capture additional meaningful requirements. Our main contribution is a generic framework that yields a fully polynomial time approximation scheme (FPTAS) for problems in this family that meet certain conditions. We use our framework to design explicit FPTASs for two such problems, namely Two-Set Subset-Sums Ratio and Factor-r Subset-Sums Ratio, with running time \(\mathcal{O}( n^4 / \varepsilon)\), which coincides with the best known running time for the original SSR problem [N. Melissinos and A. Pagourtzis, Lect. Notes Comput. Sci. 10976, 602–614 (2018; Zbl 1509.68338)].

Cited in 1 Document

MSC:

68W25 Approximation algorithms
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

approximation scheme; subset-sums ratio; knapsack problems; combinatorial optimization

Citations:

Zbl 1509.68338
Cite Review PDF
Full Text: DOI

References:

[1] Bazgan, Cristina; Santha, Miklos; Tuza, Zsolt, Efficient approximation algorithms for the subset-sums equality problem, J. Comput. Syst. Sci., 64, 2, 160-170 (2002) · Zbl 1078.90037
[2] Bringmann, Karl; Nakos, Vasileios, A fine-grained perspective on approximating subset sum and partition, (Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021 (2021), SIAM), 1797-1815 · Zbl 07788446
[3] Chan, Timothy M., Approximation schemes for 0-1 knapsack, (1st Symposium on Simplicity in Algorithms. 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA. 1st Symposium on Simplicity in Algorithms. 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA, OASICS, vol. 61 (2018), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 5:1-5:12 · Zbl 1433.68613
[4] Cieliebak, Mark; Eidenbenz, Stephan J., Measurement errors make the partial digest problem NP-hard, (LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings. LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings, Lecture Notes in Computer Science, vol. 2976 (2004), Springer), 379-390 · Zbl 1196.68100
[5] Cieliebak, Mark; Eidenbenz, Stephan J.; Pagourtzis, Aris, Composing equipotent teams, (Fundamentals of Computation Theory, 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings. Fundamentals of Computation Theory, 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings, Lecture Notes in Computer Science, vol. 2751 (2003), Springer), 98-108 · Zbl 1278.68104
[6] Cieliebak, Mark; Eidenbenz, Stephan J.; Pagourtzis, Aris; Schlude, Konrad, Equal sum subsets: Complexity of variations (2003), ETH Zürich, Department of Computer Science, Technical report 370 · Zbl 1187.68248
[7] Cieliebak, Mark; Eidenbenz, Stephan J.; Penna, Paolo, Noisy data make the partial digest problem NP-hard, (Algorithms in Bioinformatics, Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003, Proceedings. Algorithms in Bioinformatics, Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003, Proceedings, Lecture Notes in Computer Science, vol. 2812 (2003), Springer), 111-123
[8] Cieliebak, Mark; Eidenbenz, Stephan J.; Pagourtzis, Aris; Schlude, Konrad, On the complexity of variations of equal sum subsets, Nord. J. Comput., 14, 3, 151-172 (2008) · Zbl 1187.68248
[9] Gens, George; Levner, Eugene, Computational complexity of approximation algorithms for combinatorial problems, (Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium. Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979. Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium. Mathematical Foundations of Computer Science 1979, Proceedings, 8th Symposium, Olomouc, Czechoslovakia, September 3-7, 1979, Lecture Notes in Computer Science, vol. 74 (1979), Springer), 292-300 · Zbl 0414.90060
[10] Gourvès, Laurent; Monnot, Jérôme; Tlilane, Lydia, Subset sum problems with digraph constraints, J. Comb. Optim., 36, 3, 937-964 (2018) · Zbl 1414.90345
[11] Horowitz, Ellis; Sahni, Sartaj, Computing partitions with applications to the knapsack problem, J. ACM, 21, 2, 277-292 (1974) · Zbl 0329.90046
[12] Horowitz, Ellis; Sahni, Sartaj, Exact and approximate algorithms for scheduling nonidentical processors, J. ACM, 23, 2, 317-327 (1976) · Zbl 0329.68041
[13] Ibarra, Oscar H.; Kim, Chul E., Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM, 22, 4, 463-468 (1975) · Zbl 0345.90049
[14] Jin, Ce, An improved FPTAS for 0-1 knapsack, (46th International Colloquium on Automata, Languages, and Programming. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. 46th International Colloquium on Automata, Languages, and Programming. 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, LIPIcs, vol. 132 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 76:1-76:14 · Zbl 07561569
[15] Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia, An efficient fully polynomial approximation scheme for the subset-sum problem, J. Comput. Syst. Sci., 66, 2, 349-370 (2003) · Zbl 1045.68157
[16] Khan, Muhammad Ali, Some Problems on Graphs and Arrangements of Convex Bodies (2017), University of Calgary, Ph.D. thesis
[17] Lipton, Richard J.; Markakis, Evangelos; Mossel, Elchanan; Saberi, Amin, On approximately fair allocations of indivisible goods, (Proceedings 5th ACM Conference on Electronic Commerce (EC-2004). Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), New York, NY, USA, May 17-20, 2004 (2004), ACM), 125-131
[18] Melissinos, Nikolaos; Pagourtzis, Aris, A faster FPTAS for the subset-sums ratio problem, (Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings. Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10976 (2018), Springer), 602-614 · Zbl 1509.68338
[19] Mucha, Marcin; Nederlof, Jesper; Pawlewicz, Jakub; Wegrzycki, Karol, Equal-subset-sum faster than the meet-in-the-middle, (27th Annual European Symposium on Algorithms. 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany. 27th Annual European Symposium on Algorithms. 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, LIPIcs, vol. 144 (2019), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 73:1-73:16 · Zbl 07525510
[20] Mucha, Marcin; Wegrzycki, Karol; Wlodarczyk, Michal, A subquadratic approximation scheme for partition, (Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 (2019), SIAM), 70-88 · Zbl 1431.68155
[21] Danupon, Nanongkai, Simple FPTAS for the subset-sums ratio problem, Inf. Process. Lett., 113, 19-21, 750-753 (2013) · Zbl 1284.68674
[22] Papadimitriou, Christos H., 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
[23] Pruhs, Kirk; Woeginger, Gerhard J., Approximation schemes for a class of subset selection problems, Theor. Comput. Sci., 382, 2, 151-156 (2007) · Zbl 1119.90077
[24] Sahni, Sartaj, Algorithms for scheduling independent tasks, J. ACM, 23, 1, 116-127 (1976) · Zbl 0326.68024
[25] Voloch, Nadav, MSSP for 2-D sets with unknown parameters and a cryptographic application, Contemp. Eng. Sci., 10, 19, 921-931 (2017)
[26] Woeginger, Gerhard J., When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?, INFORMS J. Comput., 12, 1, 57-74 (2000) · Zbl 1034.90014
[27] Woeginger, Gerhard J.; Yu, Zhongliang, On the equal-subset-sum problem, Inf. Process. Lett., 42, 6, 299-302 (1992) · Zbl 0772.68059
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.