Cours/Séminaire
Notice
Lieu de réalisation
Paris
Langue :
Anglais
Crédits
François Baccelli (Publication), Céline Compte (Intervention)
Détenteur des droits
Inria
Conditions d'utilisation
Droit commun de la propriété intellectuelle
Citer cette ressource :
Céline Compte. Inria. (2022, 17 janvier). Stochastic Dynamic Matching in Graphs , in DYOGENE/ERC NEMO 2022 : Seminar series. [Vidéo]. Canal-U. https://www.canal-u.tv/147496. (Consultée le 15 juin 2024)

Stochastic Dynamic Matching in Graphs

Réalisation : 17 janvier 2022 - Mise en ligne : 17 janvier 2022
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

In this presentation, we will consider a stochastic dynamic matching model, in which items of different classes arrive according to independent Poisson processes, and compatibilities between items are described by an undirected graph on their classes.  We will first focus on a specific matching policy called first-come-first-matched. Our main contribution is the observation that, under this policy, the matching model is equivalent to an order-independent (loss) queue, a model that has recently gained momentum in the queueing-theory literature. Using this equivalence, we will formulate simpler proofs for several existing results and derive closed-form expressions for performance metrics like the matching rate along an edge and the waiting probability of a class. In a second time, we will use results from graph theory and linear algebra to characterize the set of achievable matching rate vectors under any matching policy.

The first part of this presentation is based on the paper “Stochastic non-bipartite matching models and order-independent loss queues” published in the journal Stochastic Models, Taylor & Francis (2022). The second part of this presentation is based on the recent preprint “Stochastic dynamic matching: a mixed graph-theory and linear-algebra approach” published in collaboration with Fabien Mathieu (LINCS) and Ana Busic (Inria and PSL University).

Intervention

Dans la même collection

Sur le même thème