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 i \in Xw_i. Bj \"{o}%DIFDELCMD < }%%% rklund , Husfeldt and Koivisto (SICOMP 2009) presented an O^\star(2^n) time algorithm for Bin Packing. In this paper, we show that for every m \in \mathbb{N there exists a constant \sigma_m >0 such that an instance of Bin Packing with m bins can be solved in O(2^{(1-\sigma_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 \delta >0 there exists an \varepsilon >0 such that if |\{ X\subseteq \{1,\ldots,n \} : w(X)=v \}| \leq 2^{(1-\varepsilon)n} for every v then |\{ w(X): X \subseteq \{1,\ldots,n\} \}|\leq 2^{\delta 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 i \in Xw_i. }%DIFDELCMD < }%%% Bj\"orklund , Husfeldt and Koivisto (SICOMP 2009) presented an 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 \sigma_m >0 such that an instance of Bin Packing with m bins can be solved in O(2^{(1-\sigma_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 \delta >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^{\delta n}.
D
Bj
D
\"{o
R
rklund
Bj\"orklund
R
\mathbb{N
\mathbf{N
R
4
4.
R
\leq
\geq
R
every
some