2 citations · 5 across the 17 of their papers we have counts for
8 papers · 1 filter
Consistency-Robustness Tradeoffs for Online Bipartite Allocation with Multiple Stages
Alexander Lindermayr, Nicole Megow, Lauren Paul
We study learning-augmented online bipartite allocation with multiple stages. In the -stage vertex-weighted fractional bipartite matching problem, demand vertices arrive in …
Better Late Than Never: Online Flow Time Scheduling with Online Estimates
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
In the classical online flow-time scheduling problem on a single machine, jobs arrive over time and must be processed to minimize the total time they spend in the system: for over…
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…