A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics

Prelegent(ci)

Céline M. F. Swennenhuis

Afiliacja

Eindhoven University of Technology

Termin

19 listopada 2020 12:15

Informacje na temat wydarzenia

online (link in the calendar and sent to the mailing list)

Seminarium

Seminarium "Algorytmika"

---

In the Bin Packing problem one is given n items with different weights
and m bins with a given capacity; the goal is to distribute the items
over the bins without exceeding the capacity.
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 there exists a constant s_m > 0
such that an instance of Bin Packing with m bins can be solved in
O((2-s_m)^n) time.
Before our work, such improved algorithms were not known even for m
equals 4.
A key step in our approach is a new result in Littlewood-Offord theory
on the additive combinatorics of subset sums.
(joint work with Jesper Nederlof, Jakub Pawlewicz Karol Węgrzycki that
will appear at SODA'21)

---