Online interval selection achieves optimal tradeoff between reliability and flexibility
Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff
Data Structures and AlgorithmsMachine Learning
Summary
This paper looks at a problem where requests come one by one, and you have to decide whether to accept intervals representing them. You might get predictions on whether these intervals belong to the best final solution. The authors find the best possible balance between two goals: being consistent with these predictions and being robust when predictions are wrong. They show this tradeoff can be tuned continuously and provide algorithms that reach the best possible guarantees under various conditions.
What this means in practice
- •For network schedulers: Improve scheduling of time intervals in networks by optimally balancing prediction accuracy and error tolerance for dynamic request sequences.
- •For cloud resource allocators: Manage allocation of computing intervals using predicted demand with tunable tradeoffs between reliability and adaptability in uncertain environments.
A theory result. No direct application yet.
Authors
Zhong Han
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.