Learning and Algorithms for Online Matching - ENSAE Paris Access content directly
Theses Year : 2023

Learning and Algorithms for Online Matching

Apprentissage et Algorithmes pour le Matching Séquentiel

Flore Sentenac
  • Function : Author
  • PersonId : 1310769
  • IdRef : 27323837X

Abstract

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
Origin : Version validated by the jury (STAR)

Dates and versions

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

Identifiers

  • HAL Id : tel-04292301 , version 1

Cite

Flore Sentenac. Learning and Algorithms for Online Matching. Statistics [math.ST]. Institut Polytechnique de Paris, 2023. English. ⟨NNT : 2023IPPAG005⟩. ⟨tel-04292301⟩
71 View
26 Download

Share

Gmail Facebook X LinkedIn More