A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, Karol Węgrzycki · SIAM Journal on Computing · 2023
Abstract. In the Bin Packing problem one is given [Formula: see text] items with weights [Formula: see text] and [Formula: see text] bins with capacities [Formula: see text]. The goal is to partition the items into sets [Formula: see text] such that [Formula: see text] for every bin [Formula: see text], where [Formula: see text] denotes [Formula: see text]. Björklund, Husfeldt, and Koivisto [ SIAM J. Comput., 39 (2009), pp. 546–563] presented an [Formula: see text] time algorithm for Bin Packing (the [Formula: see text] notation omits factors polynomial in the input size). In this paper, we show that for every [Formula: see text] there exists a constant [Formula: see text] such that an instance of Bin Packing with [Formula: see text] bins can be solved in [Formula: see text] randomized time. Before our work, such improved algorithms were not known even for [Formula: see text]. A key step in our approach is the following new result in Littlewood–Offord theory on the additive combinatorics of subset sums: For every [Formula: see text] there exists an [Formula: see text] such that if [Formula: see text] for some [Formula: see text], then [Formula: see text].