论文标题
关于几乎所有子集总和问题的硬度
On the Hardness of Almost All Subset Sum Problems by Ordinary Branch-and-Bound
论文作者
论文摘要
给定$ n $阳性整数$ a_1，a_2，\ dots，a_n $和一个正整数右手$β$，我们考虑了子集总和问题的可行性版本，这是确定$ a_1，a_2，a_2，\ dots，a_n $的子集的问题。我们表明，如果将右侧$β$选择为$ \ lfloor r \ sum_ {j = 1}^n a_j \ rfloor $对于常数$ 0 <r <1 $，并且如果$ a_j $ and $ a_j $是独立的，则是独立的，并且是从相同的分布中分布的，并且是从均匀的分布中分布的，该分布来自一个离散的分布$ {1,2，\ d/\ dots \ dots \ lffor {\ lforor { } $，然后生成子集总和问题的实例的概率需要在单个变量上以任何顺序分支在任何顺序上分支为$ 1 $ as a $ n $时，就需要创建指数数的分支和结合节点。
Given $n$ positive integers $a_1,a_2,\dots,a_n$, and a positive integer right hand side $β$, we consider the feasibility version of the subset sum problem which is the problem of determining whether a subset of $a_1,a_2,\dots,a_n$ adds up to $β$. We show that if the right hand side $β$ is chosen as $\lfloor r\sum_{j=1}^n a_j \rfloor$ for a constant $0 < r < 1$ and if the $a_j$'s are independentand identically distributed from a discrete uniform distribution taking values ${1,2,\dots,\lfloor 10^{n/2} \rfloor }$, then the probability that the instance of the subset sum problem generated requires the creation of an exponential number of branch-and-bound nodes when one branches on the individual variables in any order goes to $1$ as $n$ goes to infinity.
