A Switching Framework for Online Interval Scheduling with Predictions

AI summary

Authors: Antonios Antoniadis (University of Twente), Ali Shahheidar (Sharif University of Technology), Golnoosh Shahkarami (Max Planck Institut für Informatik, Universität des Saarlandes), Abolfazl Soltani (Sharif University of Technology) arXiv: 2511.16194v1 [cs.LG], 20 Nov 2025 | License: CC BY 4.0

Overview

Research area: Online algorithms / learning-augmented algorithms (algorithms with predictions), applied to interval scheduling. Technical level: Advanced — the paper is a theoretical computer science contribution built on competitive-ratio analysis, consistency/robustness trade-offs, and matching upper and lower bounds. Scope: The paper designs and analyzes frameworks that combine machine-learned predictions with classical online interval scheduling algorithms in the irrevocable, proportional-weight setting, and characterizes the achievable consistency–robustness trade-off.

What This Paper Is About

In online interval scheduling, intervals (each with a release time and a deadline) arrive one at a time, and the algorithm must immediately and irrevocably accept or reject each interval without knowing what comes next, while never accepting two overlapping intervals. The goal is to maximize the total length of the accepted intervals. Because no online algorithm can achieve a constant competitive ratio in the general setting, the authors study a learning-augmented version in which the algorithm also receives predictions — and ask how to use those predictions to do better when they are accurate, while still remaining safe when they are wrong.

Key Contributions

1. The Trust-and-Switch framework: A general mechanism that starts by following predictions blindly (the trust phase) and irreversibly switches at most once to a classical algorithm (the independent phase) once the prediction is provably inaccurate. It achieves 1-consistency and, when the post-switch algorithm is θ-competitive, guarantees |Opt| ≤ θ·|Alg| + 2k, where k is the maximum interval length.
2. The SemiTrust-and-Switch framework: A tunable refinement that follows the prediction only for intervals shorter than a threshold τ and accepts longer intervals greedily, interpolating between fully trusting and fully ignoring the prediction. It achieves (1 + k/τ)-consistency and, with a θ-competitive post-switch algorithm, |Opt| ≤ max(θ, Δ+1)·|Alg| + τ, where Δ is the ratio of the longest to the shortest interval length.
3. Lower bounds: Matching bounds for two-value instances showing that any (1+α)-consistent algorithm Alg′ with α < (⌈Δ⌉ − 1)/Δ must incur a robustness loss of at least Δ·|Alg′| + k, even given full predictions — establishing that Trust-and-Switch is optimal for this class of instances. A lower bound for SemiTrust-and-Switch is also provided.
4. The SmoothMerge algorithm: A randomized algorithm that probabilistically merges a prediction-based strategy and a greedy strategy, achieving robustness plus smoothness (graceful degradation as prediction quality worsens), with an expected-value guarantee expressed in terms of the prediction error η and the probabilities p_t and p_g.

Main Findings

• 1-consistency of Trust-and-Switch: The paper proves (Lemma 1) that whenever the predictions are accurate, the framework never switches, so it matches the predicted (optimal) solution exactly. The proof shows that any switch would imply the prediction was not optimal.
• Robustness bound of Trust-and-Switch: The optimal offline value is bounded by θ·|Alg| + 2k, where θ is the competitive ratio of the classical algorithm used after the switch. The additive 2k accounts for losses incurred while trusting inaccurate predictions and during the transition; the multiplicative term comes from the post-switch algorithm.
• Tunable consistency–robustness trade-off in SemiTrust-and-Switch: Consistency is (1 + k/τ) and robustness is max(θ, Δ+1)·|Alg| + τ. The threshold τ exposes an explicit dial between the two.
• More information does not help: The lower bounds are proved under the stronger full-information prediction setting (Î, which supplies predicted release times and deadlines for all intervals) yet match the guarantees achievable with the weaker binary setting (Ô, which merely suggests accept or reject per interval). Access to more detailed predictions, or receiving them offline, does not improve the achievable guarantees.
• Tightness for two-value instances: Any (1+α)-consistent algorithm with α < (⌈Δ⌉ − 1)/Δ suffers robustness loss of at least Δ·|Alg′| + k, matching the Trust-and-Switch guarantee for this class — the framework is optimal even with full predictions.
• SmoothMerge guarantee: With η denoting prediction error, E[|Alg|] ≥ max{ |Opt|·(1−η)·p_t·(1−p_g), ((p_g − p_t·p_g)/(1 − p_t·p_g))·|Greedy| }. This simultaneously delivers robustness versus Greedy and graceful degradation (smoothness) as η grows.
• Gap filled in the literature: Prior prediction-based work covered the unit-weight case (Boyar et al., 2023) and proportional weights with revocable decisions (Karavasilis, 2025). This paper addresses proportional weights with irrevocable decisions.
• Experiments mentioned but not detailed in the provided content: The introduction states that the authors provide experimental results on real-world data; the specific datasets, benchmarks, and numerical outcomes are not reported in the content available here.

Methodology in Plain English

The authors build algorithms by combining two existing strategies: one that follows the prediction ("Trust") and one classical algorithm that ignores predictions entirely (for example, a greedy algorithm). The central design question is how and when to move from one to the other.

• Switching based on an online audit. At each interval arrival, the framework computes an evaluation point — essentially "the latest deadline among predicted-accepted intervals released so far," or the current release time if no such interval is active. At that point it checks two things: whether the predicted-accepted intervals are mutually non-overlapping, and whether the length of the offline optimum on the instance seen so far exceeds the length of the blindly-trusted prediction. If either check fails, the prediction is provably wrong, and the algorithm switches permanently to the classical algorithm. Because the comparison is against an offline optimum on data already observed, the check is computable online.
• Proving the guarantee. To bound robustness, the paper partitions all intervals into three classes relative to the switching time t_j: intervals fully before t_j (ℐ₁), intervals straddling t_j (ℐ₂), and intervals starting after t_j (ℐ₃). Class ℐ₁ is bounded by an additive k, class ℐ₂ by another additive k (all such intervals contain the point t_j, so at most one can be chosen), and class ℐ₃ is handled multiplicatively by the θ-competitive post-switch algorithm.
• Getting a tunable dial. Instead of trusting all predictions, SemiTrust-and-Switch trusts only intervals shorter than τ and handles longer ones greedily. This limits the damage a bad prediction can do, trading a small consistency loss for better robustness.
• Merging instead of switching, at random. SmoothMerge runs both strategies in parallel on the same input. When they agree, it follows them; when they disagree, it accepts with probabilities p_t and p_g. This averaging produces an expected guarantee that degrades smoothly (linearly in the prediction error η) rather than falling off a cliff.
• Proving impossibility. Lower bounds are constructed via carefully designed two-value instances that force any sufficiently consistent algorithm to lose at least Δ·|Alg′| + k, showing the framework cannot be beaten.

Why This Matters

The paper closes a structural gap in the theory of interval scheduling with predictions: earlier work covered unit weights with predictions, or proportional weights only in the revocable setting. By treating the irrevocable proportional-weight case and providing both matching upper and lower bounds, it establishes exactly how much consistency and robustness can be achieved — and shows that richer predictions do not buy better guarantees, which is a meaningful negative result for practitioners deciding how much prediction machinery to build.

Real-world applications named in the paper:

• Computing resource management
• Manufacturing systems
• Real-time service scheduling
• Vehicle routing and satellite communication scheduling (cited via Bar-Noy et al., 1999)

Industry relevance: Systems that admit or reject jobs on arrival — schedulers, resource allocators, and service dispatch platforms — often have a forecasting model available but cannot tolerate catastrophic performance when the forecast is wrong. Frameworks that guarantee a worst-case bound while exploiting accurate forecasts are directly relevant to that operational requirement. The finding that full, offline predictions do not outperform simple binary per-interval predictions suggests that simpler prediction pipelines may suffice in deployment.

Future Directions

• Experimental validation at scale. The paper states that experimental results on real-world data are provided, but the specifics (datasets, metrics, comparisons) are not in the content reviewed here; a natural step is to characterize how SmoothMerge and SemiTrust-and-Switch behave on real scheduling traces and how one should set τ, p_t, and p_g in practice.
• Closing the remaining lower-bound gap for SemiTrust-and-Switch. A lower bound is given for the framework, but whether it matches the upper bound across all regimes (not just the two-value instances analyzed for Trust-and-Switch) is an open question.
• Beyond binary and full information. Since the results show extra prediction detail does not help, a natural question is what other forms of advice (for example, partial or noisy structural information) could actually improve the achievable trade-off.
• Extensions to related scheduling variants. The related work covers revocable, any-order, sorted-order, and weighted interval scheduling; transferring the switching/merging machinery to those settings, and to weighted objectives with arbitrary weights (where no finite competitive ratio is known in general), remains open.

Target Audience

Researchers in online algorithms, learning-augmented algorithms, and beyond-worst-case analysis; graduate students working on scheduling theory, competitive analysis, or algorithms with predictions; and theoretically inclined practitioners in scheduling, resource allocation, and operations research who want rigorous consistency/robustness guarantees before adopting forecasting-based decision rules.

Authors’ abstract

We study online interval scheduling in the irrevocable setting, where each interval must be immediately accepted or rejected upon arrival. The objective is to maximize the total length of accepted intervals while ensuring that no two accepted intervals overlap. We consider this problem in a learning-augmented setting, where the algorithm has access to (machine-learned) predictions. The goal is to design algorithms that leverage these predictions to improve performance while maintaining robust guarantees in the presence of prediction errors. Our main contribution is the SemiTrust-and-Switch framework, which provides a unified approach for combining prediction-based and classical interval scheduling algorithms. This framework applies to both deterministic and randomized algorithms and captures the trade-off between consistency (performance under accurate predictions) and robustness (performance under adversarial inputs). Moreover, we provide lower bounds, proving the tightness of this framework in particular settings. We further design a randomized algorithm that smoothly interpolates between prediction-based and robust algorithms. This algorithm achieves both robustness and smoothness--its performance degrades gracefully with the quality of the prediction.