Back to Search
Start Over
BETTER BIN PACKING APPROXIMATIONS VIA DISCREPANCY THEORY.
- Source :
-
SIAM Journal on Computing . 2016, Vol. 45 Issue 3, p930-946. 17p. - Publication Year :
- 2016
-
Abstract
- 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]
- Subjects :
- *POLYNOMIALS
*ALGORITHMS
*APPROXIMATION theory
*LINEAR equations
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 45
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 116887930
- Full Text :
- https://doi.org/10.1137/140955367