A Fine-Grained Perspective on Approximating Subset Sum and Partition

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 Subset Sum 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 Subset Sum 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 Subset Sum, which yields a mildly subquadratic randomized approximation scheme.

For the related Partition problem, an important special case of Subset Sum, 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 Subset Sum 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}).

--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807

Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.