论文标题
重新访问随机子集总和问题
Revisiting the Random Subset Sum problem
论文作者
论文摘要
可以通过其随机版本的方式来研究众所周知的子集总和问题的平均属性，在该版本中，我们将获得目标值$ z $，随机变量$ x_1，\ ldots，x_n $和错误参数$ \ varepsilon> 0 $，并且我们寻求$ x_i $的子集$ x_i $ s $ z $ z $ z $ s $ s olor $ var cor var cor var for vareps。在此设置中，已经表明，在对随机变量的分布中的轻度假设下，大小$ \ MATHCAL {O}的样本（\ log（\ log（1/\ varepsilon））$足以获得，具有很高的可能性，近似于$ [-1/2，1/2] $中所有值的近似值。最近，该结果已在算法社区之外重新发现，从而在其他领域实现了有意义的进步。在这项工作中，我们为该定理提供了另一种证据，采用更直接的方法和对更多基本工具的资源。
The average properties of the well-known Subset Sum Problem can be studied by the means of its randomised version, where we are given a target value $z$, random variables $X_1, \ldots, X_n$, and an error parameter $\varepsilon > 0$, and we seek a subset of the $X_i$s whose sum approximates $z$ up to error $\varepsilon$. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size $\mathcal{O}(\log(1/\varepsilon))$ suffices to obtain, with high probability, approximations for all values in $[-1/2, 1/2]$. Recently, this result has been rediscovered outside the algorithms community, enabling meaningful progress in other fields. In this work we present an alternative proof for this theorem, with a more direct approach and resourcing to more elementary tools.
