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.