Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio

Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos, Nikos Leonardos, Aris Pagourtzis, Christos Pergaminelis, Stavros Petsalakis, Kanellos Tsitouras · 2025

Read Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio by Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos, Nikos Leonardos, Aris Pagourtzis, Christos Pergaminelis, Stavros Petsalakis, Kanellos Tsitouras (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18241.txt.

Introduction

Sotiris Kanellopoulos, Giorgos Mitropoulos, and six co-authors design near-optimal algorithms for fair splitting problems. Their paper, from twenty twenty-five, studies the k-subset sum ratio problem. Given a bag of positive numbers, choose k disjoint groups whose sums are as equal in ratio as possible. Perfect balance is hard to compute exactly.

Their scheme guarantees answers within any set error margin. Its runtime grows in a controlled way with group count and precision. A second problem forces the groups to cover every number. That version, tied to envy-free division, gets its own scheme. Both are the first of their kind for more than two groups.

Catalog record

CREATORSotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos, Nikos Leonardos, Aris Pagourtzis, Christos Pergaminelis, Stavros Petsalakis, Kanellos Tsitouras
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-18241

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximation Schemes for k-Subset Sum Ratio and k-way Number Partitioning Ratio Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos, Nikos Leonardos, Aris Pagourtzis, Christos Pergaminelis, Stavros Petsalakis, Kanellos Tsitouras Abstract The Subset Sum Ratio problem (SSR) asks, given a multiset A A of n n positive integers, to find two disjoint subsets of A A such that the largest-to-smallest ratio of their sums is minimized. In this paper we study the k k -version of SSR, namely k k - Subset Sum Ratio ( k k -SSR), which asks to minimize the largest-to-smallest ratio of sums of k k disjoint subsets of A A . We develop approximation schemes for k k -SSR running in O ⁡ ( n 2 ​ k / ε k − 1 ) O({n^{2k}}/{\varepsilon^{k-1}}) and O ~ ​ ( n / ε 3 ​ k − 1 ) \widetilde{O}(n/{\varepsilon^{3k-1}}) time, by expanding known techniques for SSR and combining them with novel ideas to address the multi-subset setting. Our second FPTAS employs carefully designed calls to the first one, being much faster than the first one when n ≫ 1 / ε n\gg 1/\varepsilon . To the best of our knowledge, these are the first FPTASs for k k -SSR for fixed k > 2 k>2 . We also study the variant of Multiway Number Partitioning in which the objective is to minimize the largest-to-smallest sum ratio of k k subsets. We extend our first FPTAS for k k -SSR to this problem through additional arguments to comply with the partitioning constraint, also achieving O ⁡ ( n 2 ​ k / ε k − 1 ) O({n^{2k}}/{\varepsilon^{k-1}}) time complexity. This represents an improvement over the best known bound of O ⁡ ( n 4 ​ k 2 + 1 / ε 2 ​ k 2 ) O(n^{4k^{2}+1}/\varepsilon^{2k^{2}}) for this problem, which stems from Nguyen and Rothe’s FPTAS Nguyen and Rothe (2014) for Minimum Envy-Ratio , although that FPTAS concerns a more general problem. keywords Fully polynomial-time approximation schemes, Subset Sum Ratio, Number Partitioning, Fair division, Envy minimization, Pseudo-polynomial time algorithms 1 Introduction The Subset Sum and Partition problems are fundamental in combinatorial optimization, with numerous applications in fair resource allocation, cryptography and scheduling. The Equal Subset Sum (ESS) problem Woeginger and Yu (1992) asks for two disjoint subsets of a given set with equal sums, while its optimization counterpart, Subset Sum Ratio (SSR) Woeginger and Yu (1992) ; Bazgan et al. (2002) , asks to minimize the ratio of sums of two disjoint subsets. These NP-hard problems arise in bioinformatics Cieliebak et al. (2003) ; Cieliebak and Eidenbenz (2004) , game theory and economics Lipton et al. (2004) ; Duetting et al. (2025) , and cryptography Zadok et al. (2024) , among others. A special case of ESS belongs to PPP Papadimitriou (1994) , which is a subclass of TFNP, further adding to the ongoing interest for these problems. In this paper we consider variations involving multiple subsets, namely k - Subset Sum Ratio ( k\text{-}\mathrm{SSR} ) and k - way Number Partitioning Ratio ( k - PART ) 1 1 1 This problem is usually referred to as ”multiway”, but we call it ” k -way” to emphasize that k is fixed. . In k\text{-}\mathrm{SSR} , the goal is to find k disjoint subsets such that the largest-to-smallest ratio of their sums is minimized, while k\text{-}\mathrm{PART} further requires these subsets to form a partition of the input. Since these problems are NP-hard, we consider approximation algorithms. In particular, we present fully polynomial-time approximation schemes (FPTASs) for both problems. Our results apply, among others, to scheduling tasks across k processors (e.g., Sahni (1976) ; Deuermeyer et al. (1982) ; Hochbaum and Shmoys (1987) ; Kanellopoulos et al. (2026) ), as well as to the fair division of indivisible goods , in particular the study of envy in discrete settings (e.g., Lipton et al. (2004) ; Nguyen and Rothe (2014) ; Kurokawa et al. (2018) and more recently Amanatidis et al. (2024) ; Springer et al. (2024) ; Zhou et al. (2024) ; Kanellopoulos et al. (2025b) ). Specifically, k\text{-}\mathrm{PART} is equivalent to the Minimum Envy-Ratio problem Lipton et al. (2004) with identical valuation functions, for which we achieve a significant improvement over (more general) earlier work Nguyen and Rothe (2014) . Related work Since Bellman’s seminal work on Subset Sum Bellman (1957) , no major improvement had occurred until a recent spike in interest culminated in various faster pseudo-polynomial algorithms Koiliaris and Xu (2019) ; Bringmann (2017) ; Jin and Wu (2019) ; Chen et al. (2024a) and FPTASs Kellerer et al. (2003) ; Gens and Levner (1994) . The ESS and SSR problems have seen recent advances, including FPTASs for SSR Nanongkai (2013) ; Melissinos and Pagourtzis (2018) ; Alonistiotis et al. (2024) ; Bringmann (2024) and an improved exact algorithm for ESS Mucha et al. (2019a) . Notably, Bringmann Bringmann (2024) provided an SSR FPTAS running in time O(n/\varepsilon^{0.9386}) , which is faster than known Subset Sum lower bounds. He achieved this in part by considering two cases based on input density. If the input is dense, a pigeonhole argument guarantees two subsets with sums within 1+\varepsilon and removing their intersection yields an approximate solution. If the input is sparse, keeping only the \mathrm{polylog}(1/\varepsilon) largest elements is proven to be sufficient for the approximation. Regarding variations of ( Equal ) Subset Sum involving k\geq 2 subsets, Antonopoulos et al. Antonopoulos et al. (2023) extend the techniques of Koiliaris and Xu (2019) ; Bringmann (2017) to provide both deterministic and randomized pseudo-polynomial algorithms. For Partition , advances include a number of (very) recent FPTASs Mucha et al. (2019b) ; Bringmann and Nakos (2021) ; Chen et al. (2024b) , with the latest work by Chen et al. Chen et al. (2025) achieving an FPTAS running in time \widetilde{O}(n+1/\varepsilon) , which is near optimal under the Strong Exponential Time Hypothesis. In Multiway Number Partitioning Bismuth et al. (2024) ; Schreiber et al. (2018) ; Korf (2010) ; Recalde et al. (2018) , different objective functions define various approaches to distributing elements among subsets, such as minimizing the maximum sum, maximizing the minimum sum, minimizing the largest-to-smallest difference of sums, or minimizing the largest-to-smallest ratio of sums. These objectives are not comparable: there are instances showing that the corresponding optimal solutions differ; we discuss this in detail in Subsection 2.2 , along with applications of each variation. Bazgan, Santha and Tuza Bazgan et al. (2002) provided the first FPTAS for SSR and demonstrated that Subset Sum Difference does not admit an FPTAS, unless \mathsf{P}=\mathsf{NP} . Similar arguments that apply to Partition have been further studied in Woeginger (2000) . Additionally, various related problems such as 3-Partition and Bin Packing are strongly NP-hard Garey and Johnson (1979) , implying that they do not admit an FPTAS or a pseudo-polynomial time algorithm unless \mathsf{P}=\mathsf{NP} . However, these problems involve a non-constant number of subsets. For our problems, we consider a fixed number k of disjoint subsets. This restriction is quite natural in applications, as it is more likely to distribute a great amount of items to a small number of agents. Sahni presents an FPTAS for Multiway Number Partitioning in

Read the complete text