论文标题
改进了（非）有界子集和分区的近似方案
Improved Approximation Schemes for (Un-)Bounded Subset-Sum and Partition
论文作者
论文摘要
我们考虑了本文中的子集总和问题及其重要变体。在子集和问题中，给出了$ n $正数的$ x $的$ x $，而目标数$ t $，其任务是找到$ x $的子集，其中最大值不超过$ t $。众所周知，这个问题是NP-HARD，并且接受了完全多项式近似方案（FPTASS）。近年来，已经表明，对于任意的小$ upuny $ gue，$ \ oo（1/ε^{2-δ}）$不存在用于任意的小$ $δ> 0 $ $的fptas（$ \ min $，+） - 卷积conjucture〜 \ cite {bringmann2021fine}。但是，如果我们放宽约束，可以绕过下限，以使任务是找到$ x $的子集，该子集略高于阈值$ t $乘以$ε$倍，并且该子集中的数字之和至少为$ 1- \ tilde \ oo（ε）$（ε）$（ε）$乘以尊重约束的最佳目标值。可能违反约束的近似方案也称为弱近似方案。对于子集总和问题，有一个随机运行的随机弱近似方案$ \ tilde \ oo（n+ 1/ε^{5/3}）$ [Mucha et al.'19]。对于特殊情况，目标$ t $是所有输入数字的总和的一半，弱近似方案等效于近似方案，这些方案不违反约束，而最著名的算法则以$ \ tilde \ oo（n+1/ε^{3} {3} {3} {3}/{2};
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 $\tilde\OO( 1/ε^{2-δ})$ for arbitrary small $δ>0$ assuming ($\min$,+)-convolution conjecture~\cite{bringmann2021fine}. 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-\tilde\OO(ε)$ 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 $\tilde\OO(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 $\tilde\OO(n+1/ε^{{3}/{2}})$ time [Bringmann and Nakos'21].
