Separating online scheduling algorithms with the relative worst order ratio

DOI10.1007/S10878-006-9005-9MaRDI QIDQ2385472zbMATH OpenOpenAlexFDO

Authors Leah Epstein, Jens S. Kohrt, Lene M. Favrholdt

Publication date 12 October 2007

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-9005-9

zbMATH Keywords

SchedulingOnline algorithmsRelative worst order ratio

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• The relative worst order ratio for online algorithms
• scientific article; zbMATH DE number 2011845
• Comparing online algorithms for bin packing problems
• The relative worst order ratio applied to paging
• The relative worst-order ratio applied to paging

Cites work

• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 2011845 (Why is no real title available?)
• scientific article; zbMATH DE number 871933 (Why is no real title available?)
• scientific article; zbMATH DE number 1445351 (Why is no real title available?)
• A Better Algorithm for an Ancient Scheduling Problem
• A lower bound for on-line scheduling on uniformly related machines
• A new measure for the study of on-line algorithms
• Algorithm Theory - SWAT 2004
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• An optimal algorithm for preemptive on-line scheduling
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Bounds for List Schedules on Uniform Processors
• New algorithms for an ancient scheduling problem.
• On-line scheduling revisited
• Preemptive Scheduling of Uniform Processor Systems
• Preemptive multiprocessor scheduling with rejection
• Preemptive on-line scheduling for two uniform processors
• Randomized on-line scheduling on two uniform machines
• Scheduling with deadlines and loss functions
• The relative worst order ratio applied to paging

Cited in

(14)

• Comparing first-fit and next-fit for online edge coloring
• Online-bounded analysis
• Scheduling jobs on grid processors
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• scientific article; zbMATH DE number 2011845 (Why is no real title available?)
• The relative worst-order ratio applied to paging
• A theoretical comparison of LRU and LRU-K
• A best on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times
• Online bounded analysis
• Relative Worst-Order Analysis: A Survey
• List factoring and relative worst order analysis
• Comparing online algorithms for bin packing problems
• A Survey of Algorithms and Models for List Update
• A new variable-sized bin packing problem

This page was built for publication: Separating online scheduling algorithms with the relative worst order ratio

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2385472)