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

Sotiris Kanellopoulos, Giorgos Mitropoulos, Antonis Antonopoulos +5

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 min…