2026-07-23T12:44:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24952 2026-02-09T08:02:31Z ddc:004 open_access

Approximation Schemes for k-Subset Sum Ratio and k-Way Number Partitioning Ratio Kanellopoulos, Sotiris Mitropoulos, Giorgos Antonopoulos, Antonis Leonardos, Nikos Pagourtzis, Aris Pergaminelis, Christos Petsalakis, Stavros Tsitouras, Kanellos Fully polynomial-time approximation schemes Subset Sum Ratio Number Partitioning Fair division Envy minimization Pseudo-polynomial time algorithms The Subset Sum Ratio problem (SSR) asks, given a multiset A of positive integers, to find two disjoint subsets of A such that the largest-to-smallest ratio of their sums is minimized. In this paper we study the k-version of SSR, namely k-Subset Sum Ratio (k-SSR), which asks to minimize the largest-to-smallest ratio of sums of k disjoint subsets of A. We develop an approximation scheme for k-SSR running in O(n^{2k}/ε^{k-1}) time, where n = |A| and ε is the error parameter. To the best of our knowledge, this is the first FPTAS for k-SSR for fixed k > 2. We also study the k-way Number Partitioning Ratio (k-PART) problem, which differs from k-SSR in that the k subsets must constitute a partition of A; this problem in fact corresponds to the objective of minimizing the largest-to-smallest sum ratio in the family of Multiway Number Partitioning problems. We present a more involved FPTAS for k-PART, also achieving O(n^{2k}/ε^{k-1}) time complexity. Notably, k-PART is also equivalent to the Minimum Envy-Ratio problem with identical valuation functions, which has been studied in the context of fair division of indivisible goods. Thus, for the case of identical valuations, our FPTAS represents a significant improvement over the O(n^{4k²+1}/ε^{2k²}) bound obtained by Nguyen and Rothe’s FPTAS [Trung Thanh Nguyen and Jörg Rothe, 2014] for Minimum Envy-Ratio with general additive valuations. Lastly, we propose a second FPTAS for k-SSR, which employs carefully designed calls to the first one; the new scheme has a time complexity of Õ(n/ε^{3k-1}), thus being much faster when n≫ 1/ ε. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sotiris Kanellopoulos and Giorgos Mitropoulos and Antonis Antonopoulos and Nikos Leonardos and Aris Pagourtzis and Christos Pergaminelis and Stavros Petsalakis and Kanellos Tsitouras 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.44 urn:nbn:de:0030-drops-249521 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.44 eng https://creativecommons.org/licenses/by/4.0/legalcode