Computer Science – Discrete Mathematics
Scientific paper
2010-07-13
Computer Science
Discrete Mathematics
Journal version of SODA'11 paper
Scientific paper
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-problem of Beck is the following. Given any 3 permutations on n symbols, color the symbols red and blue, such that in any interval of any of those permutations, the number of red and blue symbols is roughly the same. The necessary difference is called the discrepancy. We establish a surprising connection between bin packing and Beck's problem: The additive integrality gap of the 3-partition linear programming relaxation can be bounded by the discrepancy of 3 permutations. Reversely, making use of a recent example of 3 permutations, for which a discrepancy of Omega(log n) is necessary, we prove the following: The O(log^2 n) upper bound on the additive gap for bin packing with arbitrary item sizes cannot be improved by any technique that is based on rounding up items. This lower bound holds for a large class of algorithms including the Karmarkar-Karp procedure.
Eisenbrand Friedrich
Pálvölgyi Dömötör
Rothvoß Thomas
No associations
LandOfFree
Bin Packing via Discrepancy of Permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bin Packing via Discrepancy of Permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bin Packing via Discrepancy of Permutations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-351387