2025/03/23 by Sotiris Kanellopoulos, Kanellopoulos, Sotiris, Giorgos Mitropoulos +13 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2503.18241
arxiv created 2026/07/30 · arxiv updated 2026/08/03
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(n2k/ε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(n2k/ε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(n4k2+1/ε2k2) 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 \widetildeO(n/ε3k-1), thus being much faster when n≫ 1/ ε.