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: Contribution to conferencePaperAcademic

Abstract

n 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 time algorithm for Bin Packing. In this paper, we show that for every m ∊ ℕ there exists a constant σm > 0 such that an instance of Bin Packing with m bins can be solved in 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.
Original languageEnglish
Pages1682-1701
DOIs
Publication statusPublished - 2021

Bibliographical note

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.

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