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

DevFeed: [Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff](<https://devfeed.tech/articles/online-interval-selection-with-binary-predictions-optimal-consistency-and-a-continuous-robustness-tradeoff-104070.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2610.37361>)

Author: Zhong Han

Published: 2026-10-28T04:00:00Z

Content type: article

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Combinatorial optimization](<https://devfeed.tech/topics/combinatorial-optimization.md>)

Tags: [consistency](<https://devfeed.tech/tags/consistency.md>), [continuous](<https://devfeed.tech/tags/continuous.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [online](<https://devfeed.tech/tags/online.md>), [predictions](<https://devfeed.tech/tags/predictions.md>), [robustness](<https://devfeed.tech/tags/robustness.md>), [selection](<https://devfeed.tech/tags/selection.md>)

## AI overview

The paper studies online interval selection where accepted requests can be revoked, but rejected or revoked requests cannot be recovered, and rewards scale with interval length. When consistency and strict robustness must hold almost surely on each fixed input, the best consistency with finite robustness is d=(3+√5)/2, including for randomized algorithms. A lower bound requires consistency above d for robustness budgets below 4φ+3~=9.472; a deterministic algorithm achieves d at exact robustness φ⁵~=11.090. Its method gives each held interval a ledger of positive prediction mass lost to irrevocable decisions. A tunable replacement cost yields a continuous family with exact consistency and exact robustness on two parameter intervals, including (25/9,10) and (4,7). In expectation, randomization can bring consistency arbitrarily close to one with finite expected robustness; under almost-sure robustness, expected consistency remains strictly above two at every finite budget.

## Source excerpt

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 $4\varphi+3\approx9.472$, whereas our deterministic algorithm attains $d$ with exact robustness $\varphi^5\approx11.090$, where $\varphi=(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.