The optimal absolute ratio for online bin packing

DOI10.1016/j.jcss.2018.11.005zbMath1421.68238OpenAlexW2909085189WikidataQ128626216 ScholiaQ128626216MaRDI QIDQ1741486

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

Publication date: 3 May 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: http://epubs.siam.org/doi/10.1137/1.9781611973730.94

zbMATH Keywords

online algorithmscompetitive ratiobin packing

Mathematics Subject Classification ID

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

Related Items (7)

Online bin packing with overload cost ⋮ Scheduling appointments online: the power of deferred decision-making ⋮ The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers ⋮ On bin packing with clustering and bin packing with delays ⋮ Several methods of analysis for cardinality constrained bin packing ⋮ More on ordered open end bin packing ⋮ Several methods of analysis for cardinality constrained bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New lower bounds for certain classes of bin packing algorithms
• An improved lower bound for on-line bin packing algorithms
• On the online bin packing problem
• A simple on-line bin-packing algorithm
• New Algorithms for Bin Packing
• Beating the Harmonic Lower Bound for Online Bin Packing
• On-line bin packing in linear time
• Optimal Analysis of Best Fit Bin Packing

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