Description
Date depot: 3 avril 2025
Titre: Greedy Learning Augmented Algorithms and Combinatorial Optimization
Directeur de thèse:
Evripidis BAMPIS (LIP6)
Encadrant :
Dimitris FOTAKIS (National Technical University of Athen)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Aide à la décision et recherche opérationnelle
Resumé: In this thesis, we propose to study the performance of greedy, priority or greedy-first algorithms from the perspective of predictions. Greedy algorithms offer simplicity, efficiency, explainability, but their worst-case guarantees are often not good. But if we can use historical data to compute a good ordering with which to consider the input, then there are greedy criteria that could lead to significantly better approximations or even the optimal solution. The (very general and perhaps too ambitious) idea is to somehow incorporate predictions into the design and operation of algorithms, at their core itself, as part of the algorithm.