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

DOI10.1016/J.ORL.2011.06.007zbMATH Open1242.90080OpenAlexW1993301069WikidataQ130471459 ScholiaQ130471459MaRDI QIDQ433121FDOQ433121

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

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

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)

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
• The largest-Z-ratio-first algorithm is 0.8531-approximate for scheduling unreliable jobs on \(m\) parallel machines
• Generalizing the Kawaguchi-Kyan bound to stochastic parallel machine scheduling
• On the integration of theoretical single-objective scheduling results for multi-objective problems

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)