BETTER BIN PACKING APPROXIMATIONS VIA DISCREPANCY THEORY.

For bin packing, the input consists of n items with sizes s1, . . . , sn ∊ [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(log2 OPT) bins. We provide the first improvement in over three decades and show that one can find a solution of cost OPT +O(logOPT · log logOPT) in polynomial time. This is achieved by rounding a fractional solution to the Gilmore-Gomory LP relaxation using the partial coloring method from discrepancy theory. The result is constructive via the algorithms of Bansal and Lovett-Meka. [ABSTRACT FROM AUTHOR]