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).
Multiprocessor scheduling with testing: Improved online algorithms and numerical experiments
2 Pith papers cite this work, alongside 2 external citations. Polarity classification is still indexing.
2
Pith papers citing it
2
external citations · OpenAlex
fields
cs.DS 2years
2026 2representative citing papers
Obligatory-test scheduling on m identical machines has deterministic competitive ratio at least 3/2 for sum of completion times, via a completion-threshold framework that also raises the single-machine lower bound from √2 to 3/2.
citing papers explorer
-
Scheduling with Testing: Competitive Algorithms for Minimizing the Total Weighted Completion Time in the Adversarial Model
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).