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}}/{\varepsilon^{k-1}})$ time, where $n=|A|$ and $\varepsilon$ 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}}/{\varepsilon^{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^2+1}/\varepsilon^{2k^2})$ bound obtained by Nguyen and Rothe's FPTAS 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 $\widetilde{O}(n/{\varepsilon^{3k-1}})$, thus being much faster when $n\gg 1/ \varepsilon$.

Abstract 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 )$$ O ( n 4 / ε ) . In particular, the exponent of n in our proposed scheme may decrease down to 2, depending on the Partition algorithm used.