Thomas Rothvoss; Approximating Bin Packing within O(log OPT * log log OPT) bins

February 1, 2013, 2:30pm LOW 102 (nonstandard date and time).
Thomas Rothvoss (faculty candidate), Department of Mathematics, MIT.

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 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.

http://www.math.washington.edu/Seminars/coll_abstracts.php#21

Leave a Reply

Your email address will not be published. Required fields are marked *