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 Wegrzycki

Onderzoeksoutput: Andere bijdrageOverige bijdrageAcademic


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.
Originele taal-2Niet gedefinieerd
StatusGepubliceerd - 2020

Bibliografische nota

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.

Citeer dit