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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

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

Original languageEnglish
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
Pages1682-1701
Number of pages20
ISBN (Electronic)9781611976465
DOIs
Publication statusPublished - 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Bibliographical note

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.

Fingerprint

Dive into the research topics of 'A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics.'. Together they form a unique fingerprint.

Cite this