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 w1, …, wn and m bins with capacities c1, …, cm. The goal is to find a partition of the items into sets S1, …, Sm such that w(Sj) ≤ cj for every bin j, where w(X) denotes Σi∊xwi. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an time algorithm for Bin Packing. In this paper, we show that for every m ∊ ℕ there exists a constant σm > 0 such that an instance of Bin Packing with m bins can be solved in 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(1–∊)n for some v then |{w(X) : X ⊆ {1, …, n}}| ≤ 2δn.