---
title: "Online Interval Selection with Binary Predictions: Optimal Consistency and a Continuous Robustness Tradeoff"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2610.37361v1"
permalink: "https://feed.astralor.com/items/itm_09ef2541ed8157204be6963b"
published: "2026-10-27T14:56:43.000Z"
score: 53
channel: "tech"
tags: ["Online Interval Selection","Binary Predictions","Optimal Consistency","Continuous Robustness Tradeoff","Requests","With","Each"]
---

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

## 速览

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 reco…

## 关键点

- 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.

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_09ef2541ed8157204be6963b