Why it is a question
THEORY-332 holds the lower bound. Bruno and Chaudhuri’s single-index rule builds once the would-be savings have risen by the build cost B above their last low, and drops once they have fallen by B below their last high. On a repeated workload whose steps are at most fB, it pays (B + fB) + B + (B + fB) per cycle against the optimum’s B. The paper’s Theorem 2 claims a factor of 3 but proves only the lower bound. Until 2026-10-20 an upper bound was THEORY-332’s promote_when.
An answer is a proof that Online-SI costs at most c(f) times the offline optimum, plus perhaps an additive constant, on every workload with steps bounded by fB, in the paper’s model (one index, fixed build cost, free drops, no space limit), together with the best such c(f). The construction shows c(f) ≥ 3 + 2f. Hill-climbing at f = 0.05 to 0.5 found nothing above it. A later rent-or-buy analysis of two-sided threshold rules would do. More random-workload simulations cannot settle it.