2025/10/16 by Chuan He, He, Changdao · 1 citation
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2510.15318
openalex publication_date 2025/10/16 · openalex created_date 2025/10/21 · openalex updated_date 2026/07/28
We study the unweighted throughput scheduling problem on a single machine in the preemption-revoke model, where a running job may be aborted at any time, but all progress is permanently lost and the job cannot be restarted. Each job Ji=(ri,pi,si) is defined by a release time ri, a processing time pi, and a slack si, and must start no later than ri+si to be feasible. We prove that no deterministic online algorithm can achieve a constant competitive ratio. The lower bound is established via an adversarial construction: starting from a three-job instance where \textsfALG completes at most one job while \textsfOPT completes all three, we iteratively nest such constructions. By induction, for every k≥ 3, there exists an instance where \textsfALG completes at most one job, while \textsfOPT completes at least k jobs. Thus, the competitive ratio can be forced to 1/k, and hence made arbitrarily close to zero. Our result stands in sharp contrast to the preemption-restart model, where Hoogeveen, Potts, and Woeginger (2000) gave a deterministic 1/2-competitive algorithm.