Approximating Bin Packing within O(log OPT · Log Log OPT) Bins
Author:
- 1 October 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 20-29
Abstract
For bin packing, the input consists of n items with sizes between 0 and 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 21 references indexed in Scilit:
- The Entropy Rounding Method in Approximation Algorithms2012
- Bin Packing via Discrepancy of Permutations2011
- 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
- Six Standard Deviations SufficeTransactions of the American Mathematical Society, 1985
- Bin packing can be solved within 1 + ε in linear timeCombinatorica, 1981
- “Integer-making” theoremsDiscrete Applied Mathematics, 1981
- Worst-Case Performance Bounds for Simple One-Dimensional Packing AlgorithmsSIAM Journal on Computing, 1974
- A Linear Programming Approach to the Cutting-Stock ProblemOperations Research, 1961