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.
In: Karlin, A.R
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
verdicts
UNVERDICTED 2representative citing papers
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.