论文标题
通过添加剂组合物数量的bin包装的更快的指数时间算法
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
论文作者
论文摘要
在垃圾箱包装问题中，给出了$ n $项目，具有$ w_1，\ ldots，w_n $和$ m $ m $ bins，具有$ C_1，\ ldots，c_m $。目标是在每个bin $ j $的$ w（s_j）\ leq c_j $中找到$ s_1，\ ldots，s_m $的分区。 Björklund，Husfeldt和Koivisto（Sicomp 2009）提出了$ \ Mathcal {o}^\ star（2^n）$ time Algorithm用于BIN包装。在本文中，我们表明，对于\ mathbf {n} $中的每一个$ m \，存在一个常数$σ_m> 0 $，这样就可以用$ m $ bins的bin填充实例在$ \ mathcal {o}（o}（2^{（1-σ_m）n}）中求解。在我们工作之前，这种改进的算法甚至以$ m $等于$ 4 $而闻名。我们方法中的关键步骤是关于子集总和的附加组合学的Littlewood-Offord理论的以下新结果：对于每一个$δ> 0 $，都存在$ \ varepsilon> 0 $，这样，如果$ | | \ | \ {x \ subseteq \ subseteq \ \ \ \ \ \ {1，\ ldots，n \ ldots，n \}，n \}：w（x） \ geq 2^{（1- \ varepsilon）n} $对于某些$ V $，然后$ | \ {w（x）：x \ subseteq \ {1，\ ldots，n \} \} | \ leq 2^{δn} $。
In the Bin Packing problem one is given $n$ items with weights $w_1,\ldots,w_n$ and $m$ bins with capacities $c_1,\ldots,c_m$. The goal is to find a partition of the items into sets $S_1,\ldots,S_m$ such that $w(S_j) \leq c_j$ for every bin $j$, where $w(X)$ denotes $\sum_{i \in X}w_i$. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an $\mathcal{O}^\star(2^n)$ time algorithm for Bin Packing. In this paper, we show that for every $m \in \mathbf{N}$ there exists a constant $σ_m >0$ such that an instance of Bin Packing with $m$ bins can be solved in $\mathcal{O}(2^{(1-σ_m)n})$ randomized time. Before our work, such improved algorithms were not known even for $m$ equals $4$. A key step in our approach is the following new result in Littlewood-Offord theory on the additive combinatorics of subset sums: For every $δ>0$ there exists an $\varepsilon >0$ such that if $|\{ X\subseteq \{1,\ldots,n \} : w(X)=v \}| \geq 2^{(1-\varepsilon)n}$ for some $v$ then $|\{ w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{δn}$.
