Séminaire Probabilités et Statistiques
Online Matching in Bipartite Random Graphs
Feb. 2023
Intervenant : Flore Sentenac
Institution : ENSAE
Heure : 15h45 - 16h45
Lieu : 3L15

Motivated by sequential budgeted allocation problems, we investigate online matching problems on classes of random graphs. In particular, we look at the so-called configuration model and geometric random graphs. We estimate the competitive ratio of the simplest algorithm, GREEDY, by approximating some relevant stochastic discrete processes by their continuous counterparts, that are solutions of an explicit system of partial differential equations. This technique gives precise bounds on the estimation errors, with arbitrarily high probability as the problem size increases. In particular, it allows the formal comparison between different configuration models. We also prove that, quite surprisingly, GREEDY can have better performance guarantees than RANKING, another celebrated algorithm for online matching that usually outperforms the former.

All (past and future) events