A Fine-Grained Perspective on Approximating Subset Sum and Partition

Approximating SubsetSum is a classic and fundamental problem in computer science and mathematical optimization. The state-of-the-art approximation scheme for SubsetSum computes a (1-ε)-approximation in time O(minn/ε, n+1/ε 2 ) [Gens, Levner'78, Kellerer et al.'97]. In particular, a (1 -1/n)-approximation can be computed in time O(n 2 ).

We establish a connection to Min-Plus-Convolution, a problem that is of particular interest in fine-grained complexity theory and can be solved naively in time O(n 2 ). Our main result is that computing a (1 -1/n)-approximation for SubsetSum is subquadratically equivalent to Min-Plus-Convolution. Thus, assuming the Min-Plus-Convolution conjecture from fine-grained complexity theory, there is no approximation scheme for SubsetSum with strongly subquadratic dependence on n and 1/ε. In the other direction, our reduction allows us to transfer known lower order improvements from Min-Plus-Convolution to SubsetSum, which yields a mildly subquadratic randomized approximation scheme. This adds the first approximation problem to the list of problems that are equivalent to Min-Plus-Convolution.

For the related Partition problem, an important special case of SubsetSum, the state of the art is a randomized approximation scheme running in time O(n + 1/ε 5/3 ) [Mucha et al.'19]. We adapt our reduction from SubsetSum to Min-Plus-Convolution to obtain a related reduction from Partition to Min-Plus-Convolution. This yields an improved approximation scheme for Partition running in time O(n+1/ε 3/2 ). Our algorithm is the first deterministic approximation scheme for Partition that breaks the quadratic barrier.