Improved Approximation Schemes for (Un-)Bounded Subset-Sum and Partition
share
We consider the SUBSET SUM problem and its important variants in this paper. In the SUBSET SUM problem, a (multi-)set X of n positive numbers and a target number t are given, and the task is to find a subset of X with the maximal sum that does not exceed t. It is well known that this problem is NP-hard and admits fully polynomial-time approximation schemes (FPTASs). In recent years, it has been shown that there does not exist an FPTAS of running time ( 1/ϵ^2-δ) for arbitrary small δ>0 assuming (min,+)-convolution conjecture <cit.>. However, the lower bound can be bypassed if we relax the constraint such that the task is to find a subset of X that can slightly exceed the threshold t by ϵ times, and the sum of numbers within the subset is at least 1-(ϵ) times the optimal objective value that respects the constraint. Approximation schemes that may violate the constraint are also known as weak approximation schemes. For the SUBSET SUM problem, there is a randomized weak approximation scheme running in time (n+ 1/ϵ^5/3) [Mucha et al.'19]. For the special case where the target t is half of the summation of all input numbers, weak approximation schemes are equivalent to approximation schemes that do not violate the constraint, and the best-known algorithm runs in (n+1/ϵ^3/2) time [Bringmann and Nakos'21].
READ FULL TEXT