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. This result
indicates that improving approximability results for bin packing requires a
better understanding of discrepancy theory.