Research

Revoke vs. Restart in Unweighted Throughput Scheduling

Related fields: Online Algorithms, Competitive Analysis

This independent research investigates the preemption–revoke model for online throughput scheduling, where a running job may be aborted but cannot be restarted. The study proves that no deterministic online algorithm can achieve a constant competitive ratio in this setting. Using an adversarial construction that recursively embeds three-job instances, it shows that the ratio can be forced arbitrarily close to zero. The result contrasts sharply with the preemption–restart model, where a 1/2-competitive deterministic algorithm is known, highlighting how irrevocable revocation fundamentally limits online schedulability.

Supervised by Professor Allan Borodin at the University of Toronto.

C. He. arXiv preprint (2025). arXiv:2510.15318