pipette
ESEspañol

Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing

Felix Buld

Preprint

In the authors' words

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 -SORT is exactly the Golden Ratio , improving the recent best-known upper bound of 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.

Main resultLimitation the authors admit

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.