Séminaire NEO: Stochastic matching and online matching algorithms

Nahuel Soprano Loto. LAAS-CNRS Date: 18 décembre 2023 Salle: Euler Bleu Abstract: In this talk, we will delve into two distinct models that originate from different backgrounds: stochastic matching models and online matching algorithms. Stochastic matching models are models in which items arrive in the system in a random fashion. The system works as an environment to put them in contact. Pairs of items present in the system can be matched based on a predefined compatibility structure between them, and once a matching occurs, the involved items leave the system. The problem behind is to schedule these matchings in order to optimize some performance criteria. In our case, this criteria will be stability, that is the property that prevents accumulation of items in the system. In the second context, online stochastic matching, the word ‘matching’ refers to something different. Given a graph, a matching is a subset of edges without extreme vertices in common. It is a classical problem to find large matchings in graphs. A new perspective, mainly motivated in internet applications, is to study online algorithms, that are the kind of algorithms that have to make decisions ‘on the fly’, or as the graph is discovered. We will focus on the case in which the underlying graph is random. We will explain how these two contexts are related, and show how the understanding of one context can help to the understanding of the second one. This work is based on the following papers: [1] M. Jonckheere, P. Moyal, C. Ramírez, and N. Soprano- Loto . Generalized Max-Weight Policies in Stochastic Matching. Stochastic Systems 2023 13:1, 40-58. [2] N. Soprano- Loto , M. Jonckheere, P. Moyal. Online matching for the multiclass stochastic block model. arXiv: [ callto:2303.15374, 2023 | 2303.15374, 2023 ] .