139 citations · 615 across the 107 of their papers we have counts for
8 papers · 1 filter
Online matching on stochastic block model
Maria Cherifa, Clément Calauzènes, Vianney Perchet
While online bipartite matching has gained significant attention in recent years, existing analyses in stochastic settings fail to capture the performance of algorithms on heteroge…
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…
Prophet Inequalities: Competing with the Top Items is Easy
Mathieu Molina, Nicolas Gast, Patrick Loiseau +1
We explore a prophet inequality problem, where the values of a sequence of items are drawn i.i.d. from some distribution, and an online decision maker must select one item irrevoca…
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…
Dynamic online matching with budget refills
Maria Cherifa, Clément Calauzènes, Vianney Perchet
Inspired by sequential budgeted allocation problems, we study the online matching problem with budget refills. In this context, we consider an online bipartite graph , w…