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(1), . . . , w(n) and m bins with capacities c 1 , . . . , c m . The goal is to find a partition of the items into sets S 1 , . . . , S m such that w(S j ) ⩽ c j for every bin j, where w(X) denotes i∈X w(i).

Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O ⋆ (2 n ) time algorithm for Bin Packing (the O ⋆ (•) notation omits factors polynomial in the input size). 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 (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 ε > 0 such that if |X ⊆ 1, . . . , n : w(X) = v| ⩾ 2 (1-ε)n for some v then |w(X) : X ⊆ 1, . . . , n| ⩽ 2 δn .