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

Online algorithmsRelative worst order ratioScheduling

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

• 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
• 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?)
• New algorithms for an ancient scheduling problem.
• On-line scheduling revisited
• Preemptive multiprocessor scheduling with rejection
• Preemptive on-line scheduling for two uniform processors
• Preemptive Scheduling of Uniform Processor Systems
• Randomized on-line scheduling on two uniform machines
• Scheduling with deadlines and loss functions
• The relative worst order ratio applied to paging

Cited in

(15)

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

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)