The optimal absolute ratio for online bin packing

DOI10.1137/1.9781611973730.94zbMath1371.68327OpenAlexW4247440730MaRDI QIDQ5363009

György Dósa, József Békési, Jiří Sgall, Rob van Stee, János Balogh

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.94

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Online algorithms; streaming algorithms (68W27)

Related Items (14)

Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty ⋮ Bounds for online bin packing with cardinality constraints ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ An asymptotic competitive scheme for online bin packing ⋮ A 4-space bounded approximation algorithm for online bin packing problem ⋮ Colored bin packing: online algorithms and lower bounds ⋮ Online two-dimensional vector packing with advice ⋮ Unnamed Item ⋮ Interior-Point-Based Online Stochastic Bin Packing ⋮ Online packing of arbitrary sized items into designated and multipurpose bins ⋮ More on batched bin packing ⋮ Fully dynamic bin packing revisited ⋮ Batch scheduling of nonidentical job sizes with minsum criteria

This page was built for publication: The optimal absolute ratio for online bin packing