Learning and Algorithms for Online Matching - ENSAE Paris Accéder directement au contenu
Thèse Année : 2023

Learning and Algorithms for Online Matching

Apprentissage et Algorithmes pour le Matching Séquentiel

Flore Sentenac
  • Fonction : Auteur
  • PersonId : 1310769
  • IdRef : 27323837X

Résumé

This thesis focuses mainly on online matching problems, where sets of resources are sequentially allocated to demand streams. We treat them both from an online learning and a competitive analysis perspective, always in the case when the input is stochastic.On the online learning side, we study how the specific matching structure influences learning in the first part, then how carry-over effects in the system affect its performance.On the competitive analysis side, we study the online matching problem in specific classes of random graphs, in an effort to move away from worst-case analysis.Finally, we explore how learning can be leveraged in the scheduling problem.
Cette thèse se concentre principalement sur les problèmes d'appariement en ligne, où des ensembles de ressources sont alloués séquentiellement à des flux de demandes. Nous les traitons à la fois du point de vue de l'apprentissage en ligne et de l'analyse compétitive, toujours lorsqueEn ce qui concerne l'apprentissage en ligne, nous étudions comment la structure spécifique de l'appariement influence l'apprentissage dans la première partie, puis comment les effets de report dans le système affectent ses performances.En ce qui concerne l'analyse compétitive, nous étudions le problème de l'appariement en ligne dans des classes spécifiques de graphes aléatoires, dans un effort pour s'éloigner de l'analyse du pire cas.Enfin, nous explorons la manière dont l'apprentissage peut être exploité dans le problème d'ordonnancement des machines.
Fichier principal
Vignette du fichier
124676_SENTENAC_2023_archivage.pdf (3.39 Mo) Télécharger le fichier
Origine Version validée par le jury (STAR)

Dates et versions

tel-04292301 , version 1 (17-11-2023)

Identifiants

  • HAL Id : tel-04292301 , version 1

Citer

Flore Sentenac. Learning and Algorithms for Online Matching. Statistics [math.ST]. Institut Polytechnique de Paris, 2023. English. ⟨NNT : 2023IPPAG005⟩. ⟨tel-04292301⟩
102 Consultations
47 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More