Corrigendum: Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling

Varun Gupta, Benjamin Moseley, Marc Uetz, Qiaomin Xie

Research output: Contribution to journalComment/Letter to the editorAcademicpeer-review

1 Citation (Scopus)
86 Downloads (Pure)

Abstract

This corrigendum fixes an incorrect claim in the paper Gupta et al. [Gupta V, Moseley B, Uetz M, Xie Q (2020) Greed works—online algorithms for unrelated machine stochastic scheduling. Math. Oper. Res. 45(2):497–516.], which led us to claim a performance guarantee of 6 for a greedy algorithm for deterministic online scheduling with release times on unrelated machines. The result is based on an upper bound on the increase of the objective function value when adding an additional job j to a machine i (Gupta et al., lemma 6). It was pointed out by Sven Jäger from Technische Universität Berlin that this upper bound may fail to hold. We here present a modified greedy algorithm and analysis, which leads to a performance guarantee of 7.216 instead. Correspondingly, also the claimed performance guarantee of (6 + 3Δ)h(Δ) in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound (7:216 + 3:608Δ)h(Δ).

Original languageEnglish
Pages (from-to)1230-1234
Number of pages5
JournalMathematics of operations research
Volume46
Issue number3
Early online date16 Jul 2021
DOIs
Publication statusPublished - Aug 2021

Keywords

  • 22/1 OA procedure

Fingerprint

Dive into the research topics of 'Corrigendum: Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling'. Together they form a unique fingerprint.

Cite this