Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff

arXiv:2610.37361v1 Announce Type: cross Abstract: We study online interval selection with binary predictions of membership in a final optimal solution. Requests arrive in arbitrary order; accepted requests may be revoked, but rejected or revoked requests cannot be recovered. With rewards proportional to interval length, the best consistency under finite strict robustness is d=(3+sqrt5)/2 when both guarantees hold almost surely on each fixed input, including for randomized algorithms. A continuous lower bound forces consistency strictly above d at every robustness budget below 4arphi+3approx9.472, whereas our deterministic algorithm attains d with exact robustness arphi^5approx11.090, where arphi=(1+sqrt5)/2. Each held interval inherits a ledger recording positive prediction mass lost through irrevocable decisions. A tunable replacement cost gives a continuous family with exact consistency throughout and exact robustness on two parameter intervals, including (C,R)=(25/9,10) and (4,7). Randomization permits expected consistency approaching one with finite expected robustness, whereas almost-sure robustness forces expected consistency strictly above two at every finite budget.

Source: arXiv cs.LG | 2026-10-28