Local matching algorithms on the configuration model
Algorithmes de mariage locaux sur le modèle de configuration
Résumé
The present thesis constructs an alternative framework to online matching algorithms on
large graphs. Using the configuration model to mimic the degree distributions of large
networks, 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 matching
policies given the degree distributions of the initial network. Towards this goal, we use a
generalization of the differential equation method to measure valued processes. Throughout
the 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.
La présente thèse construit un cadre alternatif aux algorithmes de mariage en ligne sur les grands graphes. En utilisant le modèle de configuration pour émuler les distributions de degrés des grands réseaux, nous construisons des algorithmes basés sur des politiques de mariage locales pour les nœuds. Ainsi, nous arrivons à prédire et à approximer les performances d'une classe de politiques de mariage étant donné la distribution de degrés initiale du réseau. Pour ce faire, nous utilisons une généralisation de la differential equation method, adaptée aux processus à valeur mesure. Pendant tout le texte, sont fournies des simulations et des comparaisons avec l'article fondamental de Karp, Vazirani et Vazirani sur lequel est basé l'approche dominante pour les mariages bipartis en ligne.
Origine : Fichiers produits par l'(les) auteur(s)