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: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)


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) 6 c j for every bin j, where w(X) denotes P iX w i. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O ?(2 n) 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}}| 6 2 δn

Originele taal-2Engels
TitelACM-SIAM Symposium on Discrete Algorithms, SODA 2021
RedacteurenDaniel Marx
Aantal pagina's20
ISBN van elektronische versie9781611976465
StatusGepubliceerd - 2021

Bibliografische nota

DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ 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.


Duik in de onderzoeksthema's van 'A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics.'. Samen vormen ze een unieke vingerafdruk.

Citeer dit