Online Interval Scheduling with Predictions

Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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 involving a pair of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. These problems have been studied under extreme settings without information about the input or with error-free advice. We study an intermediate setting with a potentially erroneous prediction that specifies the set of intervals/requests forming the input sequence. For both problems, we provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. For disjoint path allocation, our results rule out the possibility of obtaining a better competitive ratio than that of a simple algorithm that fully trusts predictions, whereas, for interval scheduling, we develop a superior algorithm. 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.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures : Proceedings of 18th International Symposium
EditorsPat Morin, Subhash Suri
Publication date2023
ISBN (Print)9783031389054
Publication statusPublished - 2023
Event18th International Algorithms and Data Structures Symposium - Montreal, QC, Canada
Duration: 31. Jul 20232. Aug 2023


Conference18th International Algorithms and Data Structures Symposium
CityMontreal, QC


  • Algorithms with prediction
  • Competitive analysis
  • Disjoint paths
  • Online interval scheduling


Dive into the research topics of 'Online Interval Scheduling with Predictions'. Together they form a unique fingerprint.

Cite this