Approximating Subset Sum Ratio faster than Subset Sum

Subset Sum Ratio is the following optimization problem: Given a set of n positive numbers I, find disjoint subsets X, Y Ď I minimizing the ratio maxtΣpXqΣpY q, ΣpY qΣpXqu, where ΣpZq denotes the sum of all elements of Z. Subset Sum Ratio is an optimization variant of the Equal Subset Sum problem. It was introduced by Woeginger and Yu in '92 and is known to admit an FPTAS [Bazgan, Santha, Tuza '98]. The best approximation schemes before this work had running time Opn 4 εq [Melissinos, Pagourtzis '18], r Opn 2.3 ε 2.6 q and r Opn 2 ε 3 q [Alonistiotis et al. '22].

In this work, we present an improved approximation scheme for Subset Sum Ratio running in time Opnε 0.9386 q. Here we assume that the items are given in sorted order, otherwise we need an additional running time of Opn log nq for sorting. Our improved running time simultaneously improves the dependence on n to linear and the dependence on 1ε to sublinear.

For comparison, the related Subset Sum problem admits an approximation scheme running in time Opnεq [Gens, Levner '79]. If one would achieve an approximation scheme with running time r Opnε 0.99 q for Subset Sum, then one would falsify the Strong Exponential Time Hypothesis [Abboud, Bringmann, Hermelin, Shabtay '19] as well as the Min-Plus-Convolution Hypothesis [Bringmann, Nakos '21]. We thus establish that Subset Sum Ratio admits faster approximation schemes than Subset Sum. This comes as a surprise, since at any point in time before this work the best known approximation scheme for Subset Sum Ratio had a worse running time than the best known approximation scheme for Subset Sum.