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

In the Bin Packing problem one is given n items with weights w ₁,..., w _n and m bins with capacities c ₁,..., c _m. The goal is to find a partition of the items into sets S ₁,..., S _m such that w(S _j) 6 c _j for every bin j, where w(X) denotes ^P _i∈ _X w _i. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O ^?(2 ⁿ) time algorithm for Bin Packing. In this paper, we show that for every m ∈ N there exists a constant σ _m > 0 such that an instance of Bin Packing with m bins can be solved in O(2 ⁽¹− ^{σ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 ε > 0 such that if |{X ⊆ {1,..., n} : w(X) = v}| > 2 ⁽¹−ε) ⁿ for some v then |{w(X): X ⊆ {1,..., n}}| 6 2 ^δn