Statistics-Econometrics-Machine Learning Seminar.

Time: 15:00 pm – 16:00 pm
Date: 28th of April 2021
Place: Online

Flore SENTENAC (CREST) – “Online Matching in Bipartite Graphs”

Abstract :

Finding large matching in bipartite graphs is a classical problem with many practical and intuitive applications: maximizing the number of students enroled in some university, the number of paired patients to kidney donors… In this talk, we are interested in the sequential version of this problem, where the vertices arrive one after the other and the matching is built on the fly, which is largely motivated by its Internet advertising display applications.

The talk will start with an introduction to the problem and its applications. We will then describe two classical algorithms used to treat the problem, namely GREEDY and RANKING. We will see how the performance of those algorithms evolves depending on the model considered. To analyze them, we will introduce classical tools in Online Algorithms Analysis and Random Graphs Theory through their application on a concrete example.

Sponsors: