{"ID":2854341,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.15318","arxiv_id":"2510.15318","title":"Revoke vs. Restart in Unweighted Throughput Scheduling","abstract":"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 $J_i=(r_i,p_i,s_i)$ is defined by a release time $r_i$, a processing time $p_i$, and a slack $s_i$, and must start no later than $r_i+s_i$ 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 $\\textsf{ALG}$ completes at most one job while $\\textsf{OPT}$ completes all three, we iteratively nest such constructions. By induction, for every $k\\ge 3$, there exists an instance where $\\textsf{ALG}$ completes at most one job, while $\\textsf{OPT}$ 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.","short_abstract":"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 $J_i=(r_i,p_i,s_i)$ is defined by a release time $r_i$, a processing time $p_i$, and a...","url_abs":"https://arxiv.org/abs/2510.15318","url_pdf":"https://arxiv.org/pdf/2510.15318v1","authors":"[\"Changdao He\"]","published":"2025-10-16T00:18:44Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}