List's worst-average-case or WAC ratio

DOI10.1007/S10951-007-0019-7MaRDI QIDQ835596zbMATH OpenOpenAlexFDO

Authors Christopher J. Osborn, Eric Torng

Publication date 28 August 2009

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

Full work available at URL https://doi.org/10.1007/s10951-007-0019-7

zbMATH Keywords

competitive analysisaverage-case analysismakespanonline schedulinglist scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• List factoring and relative worst order analysis
• List Factoring and Relative Worst Order Analysis
• Ratio List Decoding
• Worst-case robust Omega ratio
• Ratio and weight quantiles
• Worst-case expected utility
• Abstract Interpretation for Worst and Average Case Analysis
• Average case selection
• The weighted sequential likelihood ratio
• Worst-case versus average-case design for estimation from partial pairwise comparisons

Cites work

• scientific article; zbMATH DE number 4130003 (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 better lower bound for on-line scheduling
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Improved Bounds for the Online Scheduling Problem
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On-line scheduling revisited

Cited in

(4)

• Machine covering in the random-order model
• Wernick's list: a final update
• Relative Worst-Order Analysis: A Survey
• Scheduling In the random-order model

This page was built for publication: List's worst-average-case or WAC ratio

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