Bin Packing via Discrepancy of Permutations

A well studied special case of bin packing is the 3-partition problem, where n items of size > 1/4 have to be packed in a minimum number of bins of capacity one. The famous Karmarkar-Karp algorithm transforms a fractional solution of a suitable LP relaxation for this problem into an integral solution that requires at most O(log n) additional bins. The three-permutations-conjecture of Beck is the following. Given any 3 permutations on n symbols, one can color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols differs only by a constant. Beck's conjecture is well known in the field of discrepancy theory. We establish a surprising connection between bin packing and Beck's conjecture: If the latter holds true, then the additive integrality gap of the 3-partition linear programming relaxation is bounded by a constant.

Published in:
Symposium on Discrete Algorithms (SODA 2011)
Presented at:
Symposium on Discrete Algorithms (SODA 2011), San Francisco, USA, January 22-25, 2011
Siam, 3600 Univ City Science Center, Philadelphia, Pa 19104-2688 Usa

 Record created 2010-11-21, last modified 2018-03-18

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)