Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing
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
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles