Corrigendum: Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling
| Autor: | Benjamin Moseley, Qiaomin Xie, Varun Gupta, Marc Uetz |
|---|---|
| Přispěvatelé: | Digital Society Institute, Mathematics of Operations Research |
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Mathematics of operations research, 46(3), 1230-1234. INFORMS Institute for Operations Research and the Management Sciences |
| ISSN: | 1526-5471 0364-765X |
| Popis: | 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 [Formula: see text] to a machine [Formula: see text] (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 [Formula: see text] in theorem 4 of Gupta et al. for the stochastic online problem has to be corrected. We obtain a performance bound [Formula: see text]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|