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

Zhong Han

cs.DSOct 27, 2026

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

Authors: Zhong Han

Organizations: Department of Biomedical Engineering, College of Design and Engineering, National University of Singapore.

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.

Figures & tables

Scope	Guarantee
Finite almost-sure robustness	$C_{\rm as}\geq d$
Budget $R_{\rm as}\leq B$	$C_{\rm as}\geq\max\{d,G(B),H(B)\}$
Optimal $C_{\rm as}=d$	$R_{\rm as}\geq 4\varphi+3$
LR (prediction-free)	$C=R=M$
SUM-BANK at $\lambda=M$	$C=d$ , $R=7\varphi+4$
Shaped-BANK	$C=d$ , $R=\varphi^{5}$

Table 1: Principal guarantees. First block: also valid for randomized algorithms with both guarantees almost surely, using

C_{\rm as},R_{\rm as}

. Second: deterministic attainments. LR is due to Garay et al. (1997) ; RP’s consistency bound to Karavasilis (2025) . The last row instead uses expected reward on fixed inputs.

Figure 1: Known performance bounds. (a) The universal lower envelope is

\max\{d,G(B),H(B)\}

; the attainable envelope combines LR with

T_{a}

. Solid

T_{a}

segments have exact robustness, dotted segments only a certificate; the shaded gap is unresolved. Near

B=6.65

, where

G

meets

d+1/20

, the lower envelope switches to

H

, which is proved only for

\gamma\leq 1/20

. The dashed LR/RP/Shaped-BANK envelope excludes interior

T_{a}

parameters; its jump at

B=\varphi^{5}

is Shaped-BANK attaining

d

. (b) At

C=d

, the three algorithm budgets are exact, while the universal minimum remains in the marked interval. Both panels concern almost-sure guarantees.

Figure 2: Universal lower-bound construction. Filled left and open right endpoints indicate half-open intervals. The common prefix forces retention of

J

and permanent rejection of every

H_{i}

; the decision on

L

selects one of two complete inputs. Both have perfect predictions and a unique optimum. The geometry uses

s=1-2\delta

t=\varphi^{-1}

, and

\delta>0

; six central pieces are drawn schematically.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Surviving branch with a long right reserve, at

\gamma=0

r=9.4

and

\varepsilon=1/20000

. Endpoint gaps are exaggerated: the schematic is not to scale, and hatching marks positive-length overlaps. Positive tiles arrive before the reserve. The forced responses retain

K

, reject

R_{0}

, switch to

J

, and reject

I,L

. The actual packing

L,I,\mathcal{A}_{0},R_{0}

approaches

4\varphi+3

, while the algorithm retains value one. If

J

is rejected, the additional positive

T

and remote completion pay the entire longer reserve; this branch is separate from the displayed history. Packing labels give the limiting lengths as

\varepsilon\downarrow 0

, not the finite instance’s exact lengths.

Root and endpoint choices	General coefficient	At $a=\alpha$
Ordinary: two eligible	$1+2m_{a}$	$4\varphi+3$
Ordinary: one eligible	$h_{0,a}+m_{a}+\rho_{a}$	$7\varphi-4$
Ordinary: none eligible	$h_{0,a}+2\rho_{a}$	$10\varphi-12$
Special: two singletons	$1+2m_{a}$	$4\varphi+3$
Special: one, $y<r$	$1+m_{a}+A_{a}$	$3\varphi+5$
Special: one, outward child	$m_{a}+1+\beta_{a}+q_{0,a}\beta_{a}$	$5\varphi+3$

Appendix

Table 2: Complete joint-cut case list. The special root is

[l,r)

and mixed choices are oriented with the singleton on the left.

K_{a}

is the maximum of the general coefficients, with the repeated

1+2m_{a}

counted once. The endpoint column preserves the specialized Shaped-BANK calculation; the largest entry there is

5\varphi+3

Algorithm	Consistency	Robustness	Error guarantee
LR	$M$	$M$ (exact)	—
RP λ , $\lambda\geq 2$	$\leq\frac{3\lambda}{\lambda-1}$	$2\lambda+2$ (exact)	—
Naive	$1$	$\infty$	$\mathrm{OPT}\leq\mathrm{ALG}+\eta_{K}$
Shaped $T_{},T_{}^{F}$	$d$	$B_{*}$ (exact)	$\mathrm{OPT}\leq d\mathrm{ALG}+\eta_{K}$
Credit $T_{c_{}},T_{c_{}}^{F}$	$d$	$B_{C*}$ (exact)	$\mathrm{OPT}\leq d\mathrm{ALG}+\eta_{K}$
SUM $S_{\varphi^{3}},S_{\varphi^{3}}^{F}$	$d$	$B_{S}$ (exact)	$\mathrm{OPT}\leq d\mathrm{ALG}+\eta_{K}$

Appendix

Table 3: Deterministic guarantees.

d=\varphi^{2}

c_{*}=\alpha^{3}

B_{*}=\varphi^{5}

B_{C*}=4\varphi+5

B_{S}=7\varphi+4

. In paired rows the error guarantee applies only to the filtered policy (superscript

F

);

\eta_{K}

uses original labels. LR is due to Garay et al. (1997) ; its interval formulation, Naive and the RP consistency bound are given by Karavasilis (2025) .

Log	Condition	Mean difference	Adjusted 99.375% CI	Win/tie/loss
NASA	Perfect	0.00006	$[0.00000,0.00019]$	2/98/0
NASA	FN .1	0.00000	$[0.00000,0.00000]$	0/100/0
NASA	FP .1	0.01227	$[0.00238,0.02129]$	72/0/28
NASA	FP 1	0.00000	$[0.00000,0.00000]$	0/100/0
CTC	Perfect	0.00776	$[0.00297,0.01375]$	17/81/2
CTC	FN .1	0.00406	$[0.00064,0.00847]$	10/89/1

Appendix

Table 4: Ledger ablation, 100 repetitions per condition. Win/tie/loss counts compare exact paired rewards; positive favors the enabled gate.

Log	Labels	Act.	LR	$\mathrm{Mix}_{C}$	$\mathrm{Mix}_{B}$	$\mathrm{SG}^{F}$
NASA	Perfect	20/20	$96.83_{-.13}^{+.14}\,/\,96.25$	$97.43_{-.10}^{+.12}\,/\,96.47$	$98.79_{-.05}^{+.05}\,/\,96.51$	$99.10_{-.09}^{+.09}\,/\,98.76$
NASA	FP 0.01923	20/20	$96.83_{-.13}^{+.14}\,/\,96.25$	$94.95_{-.15}^{+.14}\,/\,85.85$	$90.75_{-.37}^{+.36}\,/\,85.41$	$97.07_{-.10}^{+.11}\,/\,96.61$
NASA	FP 0.1	0/20	$96.83_{-.13}^{+.14}\,/\,96.25$	$91.66_{-.18}^{+.20}\,/\,69.28$	$80.11_{-.44}^{+.44}\,/\,67.55$	$94.36_{-.20}^{+.20}\,/\,93.60$
NASA	FP 1	0/20	$96.83_{-.13}^{+.14}\,/\,96.25$	$90.21_{-.11}^{+.12}\,/\,61.36$	$75.42_{-.24}^{+.24}\,/\,61.00$	$89.12_{-.28}^{+.27}\,/\,87.84$
CTC	Perfect	20/20	$93.27_{-.11}^{+.10}\,/\,92.77$	$94.55_{-.08}^{+.08}\,/\,92.86$	$97.43_{-.04}^{+.04}\,/\,92.99$	$95.58_{-.14}^{+.14}\,/\,94.83$
CTC	FP 0.0034	20/20	$93.27_{-.11}^{+.10}\,/\,92.77$	$91.74_{-.15}^{+.15}\,/\,84.26$	$88.33_{-.39}^{+.42}\,/\,83.22$	$93.80_{-.17}^{+.16}\,/\,92.95$

Appendix

Table 5: Random-order reward, percent of optimum (20 inputs per condition). Each cell is

\text{mean}_{-\ell}^{+u}\,/\,q_{.05}

: the pointwise 95% bootstrap interval is

[\text{mean}-\ell,\text{mean}+u]

;

q_{.05}

is the empirical individual-run fifth percentile: the sample minimum for each deterministic method, and the weighted quantile of 40 branch outcomes for each mixture. Mix C , Mix B use

\pi=\alpha^{2}/2

1/\varphi

in Section 7 (expected consistency

d

, resp. robustness

\varphi^{5}

); means integrate the coin. Act. counts inputs with

\eta_{K}<(4-2\varphi)\mathrm{OPT}

(Appendix O ). SG denotes Shaped-BANK;

\mathrm{SG}^{F}

is filtered SG. These are exploratory fixed-log summaries.

Log	Labels	SG F	SG	Scalar F	SUM F	MAX( $\varphi^{3}$ )	LR	Half(4)	RP F
NASA	Perfect	99.10	99.10	99.10	99.17	98.93	96.83	99.26	98.67
NASA	FP .1	94.36	94.92	94.35	92.26	96.20	96.83	93.15	91.76
NASA	FP 1	89.12	88.63	89.08	88.56	93.07	96.83	89.01	88.17
CTC	Perfect	95.58	95.58	95.58	95.91	95.51	93.27	97.22	92.80
CTC	FP .1	89.25	89.68	89.24	87.34	90.63	93.27	86.84	87.24
CTC	FP 1	86.39	85.72	86.37	85.73	89.15	93.27	86.12	85.37

Appendix

Table 6: Mean retained reward (% of OPT; twenty shared repetitions per cell). Shaped-BANK (SG) and RP at

\lambda=(5\varphi+1)/2

share exact robustness

5\varphi+3

. Superscript

F

denotes permanent filtering. The best scalar Credit uses

c_{*}=2\varphi-3

and budget

4\varphi+5

; SUM has budget

7\varphi+4

; MAX(

\varphi^{3}

) is a descriptive comparator. Credit at

c=\varphi/2

is included in the full comparison tables.

Figure 4: Main-regime rewards: NASA/CTC rows and FN/FP columns. The eight methods are raw/filtered SG, filtered best scalar Credit, filtered SUM, MAX(

\varphi^{3}

), LR, Half(4), and filtered RP at the SG robustness budget. Points are twenty-repetition means with pointwise 95% bootstrap intervals (10,000 shared resamples). Perfect labels appear in both columns; FN and FP flip different classes. The FP perfect-to-

0.1

segment is omitted because the low-FP regime lies between them. Methods have different guarantee budgets; MAX is descriptive. Raw/filtered SG coincide in the FN panels, while filtered SG and scalar Credit nearly overlap at this scale.

Figure 5: Bounded low-FP study. Top: mean original-label

\eta_{K}/\mathrm{OPT}

with pointwise bootstrap intervals; dashed line: SG’s exact activation threshold

4-2\varphi

. Bottom: actual activation counts out of twenty with pointwise Wilson intervals. Dotted vertical references mark the analytic expected-error crossings,

.03700

and

.00655

; the measured grid was fixed around the Credit crossings. Rates share nested labels and reveal orders. Mean-error crossing and realization-level activation are distinct quantities.

Quantity	NASA	CTC
Data records	18,239	77,222
Excluded zero-runtime records	173	17
Retained intervals	18,066	77,205
Exact optimum $V$	5,816,181	28,353,920
Fixed optimal-set size (FN eligible)	3,635	1,464
Complement size (FP eligible)	14,431	75,741

Appendix

Table 7: Fixed workload-derived instances. Exact objectives are seconds.

Condition	Naive	LR	$\mathrm{Mix}_{C}$	$\mathrm{Mix}_{B}$	SG	$\mathrm{SG}^{F}$
Perfect	100.00	94.98	95.94	98.08	95.61	95.61
FP .0068	95.05	94.98	94.99	95.02	95.30	95.28
FP .1	78.11	94.98	91.76	84.55	94.10	93.57

Appendix

Table 8: CTC submission-order sensitivity. Mean percentages of the fixed optimum;

n=1

for perfect labels and

n=20

for each nonzero FP rate. The initial coin is integrated for both mixture columns.

Quantity	NASA	CTC
Precision / recall	$.851/.660$	$.428/.426$
Weighted recall	$.610$	$.364$
$\eta_{K}/\mathrm{OPT}$	$.577$	$1.574$
Active error branch	$6/7$	$0/31$
Shaped / filtered	$94.58/94.58$	$89.81/89.66$
SUM / MAX at $\varphi^{3}$	$95.17/95.17$	$89.43/89.95$

Appendix

Table 9: Held-out learned-label checks. Precision/recall pool request counts; weighted recall and

\eta_{K}/\mathrm{OPT}

pool lengths. Reward rows are means of block percentages. The selected threshold maximizes validation F1, not the online objective.

Condition	NASA	CTC
Ordinary score, F1-selected	94.58	89.66
Ordinary score, error-selected	93.71	90.30
Ordinary score, reward-selected	96.96	90.30
Cost score, F1-selected	93.13	90.21
Cost score, error-selected	94.91	90.30
Cost score, reward-selected	96.96	90.48

Appendix

Table 10: Secondary objective-alignment diagnostic. Entries are mean block percentages for filtered SG on the same 7 NASA and 31 CTC test blocks. Reward selection uses only validation blocks. Threshold 1 gives all-negative labels on these scores.

	128 suffixes	No MC	No MC	No MC
Method	% OPT	% OPT	Retained	Revoked
Conditional	94.334	94.817	13.76302	4.86719
Pooled	94.474	94.458	13.68750	4.91406
Uniform	94.143	94.423	13.68229	4.66406
Known law	94.660	94.665	13.74740	4.89063
Myopic	—	90.652	12.91667	2.45313

Appendix

Table 11: Fixed all-negative-reference attribution cohort: six Context trials and 384 test episodes. No-MC columns use certified finite expectations on the same models and episodes as the 128-suffix column. Retained and revoked lengths are in the original interval units; the primary paired outcome is retained length.

Predeclared comparison	Mean difference	Trial-level 95% interval
Conditional $-$ uniform (primary)	$+.003255$	$[-.041704,+.048214]$
Conditional $-$ pooled	$-.010417$	$[-.053072,+.032239]$
Conditional $-$ swapped	$+.024740$	$[-.033268,+.082747]$
Uniform $-$ myopic	$+.462891$	$[+.375407,+.550374]$
Known law $-$ uniform	$+.019531$	$[-.019780,+.058843]$

Appendix

Table 12: Independent Context cohort: 24 training trials and 1,536 test episodes. Differences are in retained-length units; Student-

t

intervals use 23 degrees of freedom. Episodes sharing a fitted model are not independent training replications.

Sequential Decision Making

Sequential Decision Making studies how to choose actions over time when outcomes, information, resources, or goals can change.

See all 139 papers

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse
Sep 9, 2026Shi Fu, Qixin Zhang, Dacheng TaoSubmodular Optimization Query Complexity
Nanyang Technological University, Singapore
Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications
Sep 4, 2026Hailiang Zhao, Xueyan Tang, Peng Chen +4Learning-Augmented Algorithms
School of Software Technology, Zhejiang University, Ningbo, China · School of Computer Science and Engineering, Nanyang Technological University, Singapore, Singapore · College of Computer Science and Technology, Zhejiang University, Hangzhou, China +1
Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift
Aug 27, 2026Fredy PokouOnline Resource Allocation Learning-Augmented Algorithms
MRE, CRIStAL · Inria, University of Lille, CNRS, Centrale Lille Villeneuve-d’Ascq, France

Sep 9, 2026J/K move · Enter open · S save

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse

Shi Fu, Qixin Zhang, Dacheng Tao

Nanyang Technological University, Singapore

Submodular Optimization Query Complexity Approximation Algorithms

Open paper AskPDF arXiv

Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most

k

available elements and changes only

O(1)

elements after each insertion. Dütting et al. [2025] established a tight

2/3

approximation with unrestricted computation and a polynomial-time

0.51

approximation. They left open at STOC 2025 whether efficient algorithms can match the offline

1-1/e

guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is

β=2-\sqrt2\approx0.5858<1-1/e.

For every

\varepsilon>0

, our randomized algorithm attains

β-\varepsilon

with

O(\varepsilon^{-2})

changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of

Ω(k)

changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold

1-(\sqrt2-1)\vartheta

, attain

1-1/e-\varepsilon

for weighted coverage with

O(\varepsilon^{-1})

recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.

Abstract

Sequential Decision Making

Explore similar work

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2−22-\sqrt{2}2−2​ Entails Exponential Queries or Linear Recourse

Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications

Learning-Augmented Online Allocation under Unreliable Advice: Robustness, Exposure Fairness, and Distribution Shift

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse