Comparing online algorithms for bin packing problems
From MaRDI portal
Publication:2434261
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
online algorithmsbin coveringbin packingbin coloringopen-end bin packingrelative worst-order ratioclass-constrained bin packing
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