Approximating Bin Packing within O(log OPT * log log OPT) bins
Author:
- Thomas RothvossTRThomas Rothvoss
Preprint
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.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- The Entropy Rounding Method in Approximation Algorithms2012
- Bin Packing via Discrepancy of Permutations2011
- Constructive Algorithms for Discrepancy Minimization2010
- Geometric Discrepancy1999
- Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problemOperations Research Letters, 1997
- Fast Approximation Algorithms for Fractional Packing and Covering ProblemsMathematics of Operations Research, 1995
- Discrepancy of Set-systems and MatricesEuropean Journal of Combinatorics, 1986
- Roth’s estimate of the discrepancy of integer sequences is nearly sharpCombinatorica, 1981
- A Linear Programming Approach to the Cutting-Stock ProblemOperations Research, 1961
- The Trim ProblemManagement Science, 1957