← 研踪 PaperTrailarXiv:2610.40554 · v1
Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing
首次提交 2026-10-30 01:39
版本更新 2026-10-30 01:39
雷达观测 2026-10-30 13:28
摘要
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 $\varphi\approx 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-30 01:39 · 最新观测版本
Exact Competitive Ratios of Index Rules for Scheduling with Obligatory Testing
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 $\varphi\approx 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.
查看此版本解读 →查看此版本原文 ↗