A Logarithmic Additive Integrality Gap for Bin Packing
From MaRDI portal
Publication:4575921
DOI10.1137/1.9781611974782.172zbMath1423.90225arXiv1503.08796OpenAlexW1910278602MaRDI QIDQ4575921
Thomas Rothvoß, Rebecca Hoberg
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.08796
Related Items (18)
On the extension complexity of scheduling polytopes ⋮ Parameterized complexity of configuration integer programs ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics ⋮ Unnamed Item ⋮ Fully-Dynamic Bin Packing with Little Repacking ⋮ On the Computational Complexity of Linear Discrepancy ⋮ Best fit bin packing with random order revisited ⋮ Linear discrepancy is \(\Pi_2\)-hard to approximate ⋮ Integer rounding and modified integer rounding for the skiving stock problem ⋮ An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case ⋮ Unnamed Item ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Online bin covering with advice ⋮ About the Structure of the Integer Cone and Its Application to Bin Packing ⋮ Best Fit Bin Packing with Random Order Revisited ⋮ From packing rules to cost-sharing mechanisms ⋮ Adaptive Bin Packing with Overflow
This page was built for publication: A Logarithmic Additive Integrality Gap for Bin Packing
