Bin Packing via Discrepancy of Permutations

DOI10.1145/2483699.2483704zbMath1301.68196arXiv1007.2170MaRDI QIDQ2933654

Dömötör Pálvölgyi, Friedrich Eisenbrand, Thomas Rothvoß

Publication date: 5 December 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.2170

zbMATH Keywords

discrepancy theory; bin packing; linear programming relaxations

Mathematics Subject Classification ID

90C05: Linear programming

68R05: Combinatorics in computer science

05A05: Permutations, words, matrices

90C27: Combinatorial optimization

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)