Publication:2933654

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

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

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 theorybin packinglinear programming relaxations

Mathematics Subject Classification ID

Linear programming (90C05) Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (13)

Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Bounds for the Nakamura number ⋮ Discrepancy theory and related algorithms ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ Set Covering with Ordered Replacement: Additive and Multiplicative Gaps ⋮ Integer rounding and modified integer rounding for the skiving stock problem ⋮ Semidefinite optimization in discrepancy theory ⋮ Better Bin Packing Approximations via Discrepancy Theory ⋮ On Capacitated Set Cover Problems ⋮ Friendly bin packing instances without integer round-up property ⋮ Algorithmic Aspects of Combinatorial Discrepancy ⋮ Minimal proper non-IRUP instances of the one-dimensional cutting stock problem

This page was built for publication: Bin Packing via Discrepancy of Permutations