Description
Date depot: 4 février 2025
Titre: Online packing with multiple predictions
Directeur de thèse:
Christoph DURR (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire
Resumé: In an online packing problem, items arrive online and have to placed so to satisfy
some packing constraint and maximize some product. Typical problems in this class are
bin packing, where items have to be packed in a minimum number of bins, such that
the total item size per bin respects the unit capacity of each bin. Another example
is call admission, where connection requests arrive only for a given telecommunication
network. Accepted requests need to be routed on a source-target path and consume some
bandwidth along the edges. Recent advances in machine learning allow to provide the
algorithm with predictions about future arriving items, allowing algorithm performances
beyond the worst case paradigm. The purpose of this thesis is to understand how an
algorithm can take benefit from multiple predictions and guarantee a competitive ratio
which degrades smoothly with the error of the best prediction.
Résumé dans une autre langue: Dans un problème d'emballage en ligne, des éléments arrivent au fur et à mesure et
doivent être placés de manière à satisfaire des contraintes de capacité et à maximiser un
certain profit. Les problèmes typiques de cette catégorie sont les suivants : bin packing,
où les éléments doivent être placés dans un nombre minimum de boîtes, afin que la taille
totale des éléments par boîte respecte la capacité unitaire de la boîte. Un autre exemple est
la gestion d'appels, où des demandes de connexions dans un réseau de télécommunication
doivent être traités dés leur arrivée. Une demande acceptée doit être acheminée sur un
chemin source-cible et consomme de la bande passante le long des arêtes du chemin.
Les avancées récentes en apprentissage automatique permettent de fournir à l'algorithme
des prédictions sur les éléments à venir, ce qui permet la conception d'algorithmes qui
dépassent le cadre d'une garantie de performance pire des cas. L'objectif de cette thèse est
de comprendre comment un algorithme peut tirer profit de plusieurs prédictions et garantir
un ratio compétitif qui se dégrade doucement avec l'erreur de la meilleure prédiction, et
ainsi proposer des outils qui combinent le meilleur des deux mondes pire de cas et cas
pratique.