Algorithmes de mariage locaux sur le modèle de configuration
Mohamed Habib Aliou Diallo Aoudi · HAL (Le Centre pour la Communication Scientifique Directe) · 2023
The present thesis constructs an alternative framework to online matching algorithms onlarge graphs. Using the configuration model to mimic the degree distributions of largenetworks, we are able to build algorithms based on local matching policies for nodes.Thus, we are allowed to predict and approximate the performances of a class of matchingpolicies given the degree distributions of the initial network. Towards this goal, we use ageneralization of the differential equation method to measure valued processes. Throughoutthe text, we provide simulations and a comparison to the seminal work of Karp,Vazirani and Vazirani based on the prevailing viewpoint in online bipartite matching.