7 papers
Non-Clairvoyant Scheduling with Progress Bars
Ziyad Benomar, Romain Cosson, Alexander Lindermayr +1
In non-clairvoyant scheduling, the goal is to minimize the total job completion time without prior knowledge of individual job processing times. This classical online optimization…
Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Ziyad Benomar, Lorenzo Croissant, Vianney Perchet +1
One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. T…
On Tradeoffs in Learning-Augmented Algorithms
Ziyad Benomar, Vianney Perchet
The field of learning-augmented algorithms has gained significant attention in recent years. These algorithms, using potentially inaccurate predictions, must exhibit three key prop…
Lookback Prophet Inequalities
Ziyad Benomar, Dorian Baudry, Vianney Perchet
Prophet inequalities are fundamental optimal stopping problems, where a decision-maker observes sequentially items with values sampled independently from known distributions, and m…
Learning-Augmented Priority Queues
Ziyad Benomar, Christian Coester
Priority queues are one of the most fundamental and widely used data structures in computer science. Their primary objective is to efficiently support the insertion of new elements…
Addressing Bias in Online Selection with Limited Budget of Comparisons
Ziyad Benomar, Evgenii Chzhen, Nicolas Schreuder +1
Consider a hiring process with candidates coming from different universities. It is easy to order candidates with the same background, yet it can be challenging to compare them oth…