An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule

DOI10.1016/J.ORL.2011.06.007MaRDI QIDQ433121zbMATH OpenOpenAlexWikidataFDO

Authors Uwe Schwiegelshohn

Publication date 13 July 2012

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2011.06.007

zbMATH Keywords

worst case analysisperformance guaranteetotal weighted completion time scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Towards a proof of the Kuzmak-Kogelman-Keller algorithm
• scientific article; zbMATH DE number 2051058
• Publication:3035528
• scientific article; zbMATH DE number 4127901
• A revised proof of the optimality for the Kise-Ibaraki-Mine algorithm
• A note on the optimality proof of the Kise-Ibaraki-Mine algorithm
• Proof of the Kurlberg-Rudnick rate conjecture
• Proof of the Kurlberg-Rudnick rate conjecture
• Proof of the Kurlberg-Rudnick Rate Conjecture
• A new proof of the Kuhn-Tucker and Farkas theorems

Cites work

• Structure of a simple scheduling polyhedron
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem

Cited in

(4)

• Improved analysis of two algorithms for min-weighted sum bin packing
• On the integration of theoretical single-objective scheduling results for multi-objective problems
• Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling
• The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines

This page was built for publication: An alternative proof of the Kawaguchi-Kyan bound for the largest-ratio-first rule

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