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

Varun Gupta (), Benjamin Moseley (), Marc Uetz () and Qiaomin Xie ()
Additional contact information
Varun Gupta: University of Chicago, Chicago, Illinois 60637
Benjamin Moseley: Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
Marc Uetz: University of Twente, Enschede 7500AE, Netherlands
Qiaomin Xie: Cornell University, Ithaca, New York 14850

Mathematics of Operations Research, 2021, vol. 46, issue 3, 1230-1234

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 ( Δ ) .

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1149 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:3:p:1230-1234

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().