A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

Abstract

In the Bin Packing problem one is given $n$ items with weights $w_1,\dots ,w_n$ and $m$ bins with capacities $c_1,\dots ,c_m$. The goal is to find a partition of the items into sets $S_1,\dots ,S_m$ such that $w(S_j)\le 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 ${\sigma }_m>0$ such that an instance of Bin Packing with $m$ bins can be solved in $\mathcal{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 $\epsilon >0$ such that if $|\{X\subseteq \{1,\dots ,n\}:w(X)=v\}|\ge 2^{(1-\epsilon )n}$ for some $v$ then $|\{w(X):X\subseteq \{1,\dots ,n\}\}|\le 2^{\delta n}$.

SODA 2021; 45 pages; 4 figures