Bin Packing via Discrepancy of Permutations
From MaRDI portal
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
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
