14 papers
Online Scheduling with a Stochastic Signal
Romain Cosson, Jingwei Li, Alexander Lindermayr +1
Nonclairvoyant scheduling is a fundamental online model in which processing times are initially unknown to the scheduler. Unfortunately, for important objectives such as total comp…
Learning-Augmented Online Scheduling with Parsimonious Preemption
Mugen Blue, Sungjin Im, Alexander Lindermayr
Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework…
The Secretary Problem with a Stochastic Precursor
Franziska Eberle, Alexander Lindermayr
In learning-augmented online algorithms, predictions are usually valued for what they say: a value estimate, a solution, or an algorithmic recommendation. This paper shows that pre…
A Simpler Analysis for -Clairvoyant Flow Time Scheduling
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We simplify the proof of the optimality of the Shortest Lower-Bound First (SLF) algorithm, introduced by Gupta, Kaplan, Lindermayr, Schlöter, and Yingchareonthawornchai [FOCS'25],…
Delayed-Clairvoyant Flow Time Scheduling via a Borrow Graph Analysis
Alexander Lindermayr, Jens Schlöter
We study the problem of preemptively scheduling jobs online over time on a single machine to minimize the total flow time. In the traditional clairvoyant scheduling model, the sche…
Online Flow Time Minimization with Gradually Revealed Jobs
Alexander Lindermayr, Guido Schäfer, Jens Schlöter +1
We consider the problem of online preemptive scheduling on a single machine to minimize the total flow time. In clairvoyant scheduling, where job processing times are revealed upon…