# Online Interval Scheduling with Predictions

arXiv: https://arxiv.org/abs/2302.13701 · HTML: https://mlsanity.com/paper/2302.13701/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2023.

## Built on by (most cited first, 1 of 1)

- [A Switching Framework for Online Interval Scheduling with Predictions](https://mlsanity.com/paper/2511.16194/) (2025)

## Abstract (arXiv)

In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each consisting of pairs of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. We study a setting with a potentially erroneous prediction specifying the set of requests forming the input sequence and provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.