TY - GEN
T1 - A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
AU - Nederlof, Jesper
AU - Pawlewicz, Jakub
AU - Swennenhuis, Céline M. F.
AU - Wegrzycki, Karol
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2020
Y1 - 2020
N2 - 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 O⋆(2n) 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(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.
AB - 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 O⋆(2n) 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(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.
M3 - Other contribution
VL - abs/2007.08204
ER -