Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.
Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi
Ola Nils Anders Svensson, Xinrui Jia
Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis