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).
Improved approximation algorithms for non-preemptive multiprocessor scheduling with testing
2 Pith papers cite this work, alongside 6 external citations. Polarity classification is still indexing.
2
Pith papers citing it
6
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
-
Hardness of Obligatory-Test Scheduling on Multiple Machines
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.