论文标题
关于密集子集总和的近线性时间算法
On Near-Linear-Time Algorithms for Dense Subset Sum
论文作者
论文摘要
在子集总和问题中，我们得到了一组$ n $正整数$ x $和一个目标$ t $，并被询问是否有$ x $ sums的某些子集到$ t $。文献中研究的此问题的自然参数是$ n $和$ t $，以及最大输入号$ \ rm {mx} _x $和所有输入号$σ_x$的总和。在本文中，我们研究了子集总和的密集情况，其中所有这些参数均为$ n $。在此制度中，标准伪多项式算法求解了多项式时间$ n^{o（1）} $中的子集总和。 我们的主要问题是：何时可以在接近线性的时间$ \ tilde {o}（n）$中求解密集的子集总和？我们通过设计改进的算法和证明有条件的下限来提供本质上完整的二分法，从而确定参数的所有设置$ n，t，\ rm {mx} _x _x _x，σ_x$，其密集子集总和在时间$ \ tilde $ \ tilde {o}（o}（o}）$。为了方便起见，我们假设不会损失一般性，$ t \ ge \ rm {mx} _x $（可以忽略较大的数字）和$ t \leσ_x/2 $（使用对称）。然后我们的二分法如下： - 通过恢复和改善Galil和Margalit [Sicomp'91]的基于添加剂的基于添加剂的方法，我们表明子集和在接近线性的时间$ \ tilde $ \ tilde {o}（n）$如果$ t \ gg \ gg \ gg \ rm {mx} _x}_xσ_x/n^2 $。 - 我们证明了一个匹配的条件下限：如果子集总和在任何设置的$ t \ ll \ rm {mx}_xσ_x/n^2 $的任何设置中，则强大的指数时间假设和强k-Sum假设失败。 我们还将算法从集合到多集，尽管具有不匹配的上限和下限。
In the Subset Sum problem we are given a set of $n$ positive integers $X$ and a target $t$ and are asked whether some subset of $X$ sums to $t$. Natural parameters for this problem that have been studied in the literature are $n$ and $t$ as well as the maximum input number $\rm{mx}_X$ and the sum of all input numbers $Σ_X$. In this paper we study the dense case of Subset Sum, where all these parameters are polynomial in $n$. In this regime, standard pseudo-polynomial algorithms solve Subset Sum in polynomial time $n^{O(1)}$. Our main question is: When can dense Subset Sum be solved in near-linear time $\tilde{O}(n)$? We provide an essentially complete dichotomy by designing improved algorithms and proving conditional lower bounds, thereby determining essentially all settings of the parameters $n,t,\rm{mx}_X,Σ_X$ for which dense Subset Sum is in time $\tilde{O}(n)$. For notational convenience we assume without loss of generality that $t \ge \rm{mx}_X$ (as larger numbers can be ignored) and $t \le Σ_X/2$ (using symmetry). Then our dichotomy reads as follows: - By reviving and improving an additive-combinatorics-based approach by Galil and Margalit [SICOMP'91], we show that Subset Sum is in near-linear time $\tilde{O}(n)$ if $t \gg \rm{mx}_X Σ_X/n^2$. - We prove a matching conditional lower bound: If Subset Sum is in near-linear time for any setting with $t \ll \rm{mx}_X Σ_X/n^2$, then the Strong Exponential Time Hypothesis and the Strong k-Sum Hypothesis fail. We also generalize our algorithm from sets to multi-sets, albeit with non-matching upper and lower bounds.
