Campus Event Calendar
Event Entry
What and Who
Approximating Bin Packing within O(log OPT * log log OPT) bins
Thomas Rothvoss
MIT
Lecture
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 17 September 2013
13:00
45 Minutes
E1 4
024
Saarbrücken
Abstract
For bin packing, the input consists of n items
with sizes s_1,...,s_n in [0,1] which have to be assigned to a minimum
number of bins of size 1. The seminal Karmarkar-Karp algorithm from '82
produces a solution with at most OPT + O(log^2 OPT) bins.
We provide the first improvement in now 3 decades and show that
one can find a solution of cost
OPT + O(log OPT * log log OPT) in polynomial time.
This is achieved by rounding a fractional solution to the
Gilmore-Gomory LP relaxation using the Entropy Method from discrepancy theory.
The result is constructive via algorithms of Bansal and Lovett-Meka.
Contact
Kurt Mehlhorn
--email hidden
passcode not visible
logged in users only
Kurt Mehlhorn, 07/19/2013 08:35 -- Created document.