Separating online scheduling algorithms with the relative worst order ratio

DOI10.1007/S10878-006-9005-9zbMATH Open1126.90022OpenAlexW1970376721MaRDI QIDQ2385472FDOQ2385472

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

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

zbMATH Keywords

SchedulingOnline algorithmsRelative worst order ratio

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Comparing first-fit and next-fit for online edge coloring
• Online-bounded analysis
• Online Bounded Analysis
• Scheduling jobs on grid processors
• Online scheduling in a parallel batch processing system to minimize makespan using restarts
• Title not available (Why is that?)
• 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
• 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)