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

Speaker(s)

Céline M. F. Swennenhuis

Affiliation

Eindhoven University of Technology

Date

Nov. 19, 2020, 12:15 p.m.

Information about the event

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

Seminar

Seminar Algorithms

---

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)

---