A Switching Framework for Online Interval Scheduling with Predictions

• URL: http://arxiv.org/abs/2511.16194v1
• Date: Thu, 20 Nov 2025 10:01:09 GMT
• Title: A Switching Framework for Online Interval Scheduling with Predictions
• Authors: Antonios Antoniadis, Ali Shahheidar, Golnoosh Shahkarami, Abolfazl Soltani,
• Abstract summary: We study online interval scheduling in the irrevocable setting, where each interval must be immediately accepted or rejected upon arrival.<n>We consider this problem in a learning-augmented setting, where the algorithm has access to (machine-learned) predictions.<n>Our main contribution is the SemiTrust-and-Switch framework, which provides a unified approach for combining prediction-based and classical interval scheduling algorithms.
• Score: 4.352962539265558
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Analyzing the effect of prediction accuracy on the distributionally-robust competitive ratio [3.616700653734583]
  We focus on the distributionally-robust competitive ratio (DRCR), introduced by Sun et al.(ICML 2024)<n>A known structural property is that, for any fixed algorithm, the DRCR decreases linearly as prediction accuracy increases.<n>We apply our results to the ski rental problem, a benchmark problem in online optimization, to identify the conditions on prediction accuracies required for the optimal DRCR.
  arXiv  Detail & Related papers  (2026-01-11T08:51:40Z)
• Relational Conformal Prediction for Correlated Time Series [56.59852921638328]
  We address the problem of uncertainty quantification in time series by exploiting correlated sequences.<n>We propose a novel distribution-free approach based on conformal prediction framework and quantile regression.<n>Our approach provides accurate coverage and achieves state-of-the-art uncertainty quantification in relevant benchmarks.
  arXiv  Detail & Related papers  (2025-02-13T16:12:17Z)
• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  We propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a user-specified profile. We apply this new approach to a well-studied online problem, namely the one-way trading problem.
  arXiv  Detail & Related papers  (2024-08-07T23:15:21Z)
• Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictions [19.537289123577022]
  We consider an online two-stage optimization with long-term constraints over a finite horizon of $T$ periods. We develop online algorithms for the online two-stage problem from adversarial learning algorithms.
  arXiv  Detail & Related papers  (2024-01-02T07:46:33Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  We propose a generalization of conformal prediction to multiple learnable parameters. We show that it achieves approximate valid population coverage and near-optimal efficiency within class. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
  arXiv  Detail & Related papers  (2022-02-22T18:37:23Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in algorithm design. We show that these predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees.
  arXiv  Detail & Related papers  (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  We introduce a general design approach for algorithms that learn predictors. We apply techniques from online learning to learn against adversarial instances, tune robustness-consistency trade-offs, and obtain new statistical guarantees. We demonstrate the effectiveness of our approach at deriving learning algorithms by analyzing methods for bipartite matching, page migration, ski-rental, and job scheduling.
  arXiv  Detail & Related papers  (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• Interpretable Machines: Constructing Valid Prediction Intervals with Random Forests [0.0]
  An important issue when using Machine Learning algorithms in recent research is the lack of interpretability. A contribution to this gap for the Random Forest Regression Learner is presented here. Several parametric and non-parametric prediction intervals are provided for Random Forest point predictions. A thorough investigation through Monte-Carlo simulation is conducted evaluating the performance of the proposed methods.
  arXiv  Detail & Related papers  (2021-03-09T23:05:55Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.