You are here

[Video] Thomas Rothvoss from Massachusetts Institute of Technology

Friday, February 1, 2013 - 2:30pm
LOW 102

Approximating Bin Packing within O(log OPT * log log OPT) bins

Thomas Rothvoss from Massachusetts Institute of Technology


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 1982 produces a solution with at most OPT + O(log^2 OPT) bins in polynomial time, where OPT denotes the value of the optimum solution.

I will describe the first improvement in 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.

I will also survey other results of mine from discrete mathematics and combinatorial optimization concerning: an approach to the Hirsch conjecture on the diameter of polytopes; the Chvatal rank of polytopes; the extension complexity of 0/1 polytopes; and the approximability of the Steiner tree problem.

People Involved: 
Event Type: 
Event Subcalendar: