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. Polarity classification is still indexing.
2
Pith papers citing it
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).
-
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.