Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing

arXiv:2610.40554 · cs.DS · Submitted 2026-10-29 · Read on arXiv

cs.DS

Submitted: 2026-10-29

Updated: 2026-10-29

License: http://creativecommons.org/licenses/by/4.0/

The gist: We revisit scheduling with obligatory testing, where each job consists of two operations: a test with an initially known time and an operation whose processing time is revealed upon completion of the…

Terminology

Abstract

We revisit scheduling with obligatory testing, where each job consists of two operations: a test with an initially known time and an operation whose processing time is revealed upon completion of the job's test. We develop an iterative competitive-ratio-preserving instance-reduction method that enables us to compute exact competitive ratios directly on highly structured instances for various index rules. Our main result is a clean analysis showing that the competitive ratio of the algorithm 1-SORT is exactly the Golden Ratio φ about 1.618, improving the recent best-known upper bound of 1.861 for arbitrary testing times. We further leverage this method to obtain near-tight bounds for a simple randomized algorithm on instances with uniform testing times.

Related papers