Comparing online algorithms for bin packing problems

DOI10.1007/s10951-009-0129-5zbMath1280.68297OpenAlexW2002739756MaRDI QIDQ2434261

Jens S. Kohrt, Leah Epstein, Lene Monrad Favrholdt

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0129-5

zbMATH Keywords

online algorithmsbin coveringbin packingbin coloringopen-end bin packingrelative worst-order ratioclass-constrained bin packing

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (11)

Online bin covering: expectations vs. guarantees ⋮ A theoretical comparison of LRU and LRU-K ⋮ Relative Worst-Order Analysis: A Survey ⋮ Online bin covering with limited migration ⋮ The evolution of rectangular bin packing problem -- a review of research topics, applications, and cited papers ⋮ List factoring and relative worst order analysis ⋮ Irreducible bin packing and normality in routing open shop ⋮ Online Bin Covering with Limited Migration ⋮ A Survey of Algorithms and Models for List Update ⋮ Comparing the costs of any fit algorithms for bin packing ⋮ Online Bin Covering: Expectations vs. Guarantees

Cites Work

• Unnamed Item
• Unnamed Item
• Tight bounds for online class-constrained packing
• The relative worst-order ratio applied to paging
• Bincoloring
• Competitive snoopy caching
• Online algorithms for a dual version of bin packing
• A new measure for the study of on-line algorithms
• Fast algorithms for bin packing
• Separating online scheduling algorithms with the relative worst order ratio
• The class constrained bin packing problem with applications to video-on-demand
• On a dual version of the one-dimensional bin packing problem
• Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
• Comparing First-Fit and Next-Fit for Online Edge Coloring
• The Ordered Open-End Bin-Packing Problem
• A simple on-line bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Algorithm Theory - SWAT 2004
• Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
• Bounds for Certain Multiprocessing Anomalies

This page was built for publication: Comparing online algorithms for bin packing problems