Presents deterministic (2.3166) and randomized (2.1523) constant-competitive algorithms for weighted single-machine scheduling with testing, extended via list scheduling to parallel machines (2.7763/2.5110).
Algorithmica (2023)
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
verdicts
UNVERDICTED 3representative citing papers
Introduces completion-threshold framework yielding first multi-machine deterministic lower bounds of 1.4811 and approaching 3/2 for obligatory-test scheduling, plus a 2-competitive algorithm.
New analysis framework yields single-machine deterministic competitive ratio of 2.316513 and randomized 2.152271, plus multi-machine bounds of 2.77629-(0.45977/m) deterministic and 2.51098-(0.3587/m) randomized.
citing papers explorer
-
The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty
New analysis framework yields single-machine deterministic competitive ratio of 2.316513 and randomized 2.152271, plus multi-machine bounds of 2.77629-(0.45977/m) deterministic and 2.51098-(0.3587/m) randomized.