Au cours des dernières décennies, la conception et l'analyse des algorithmes étaient basées sur l'analyse du pire cas, où la performance d'un algorithme est caractérisée par sa pire performance sur toutes les instances d'une taille donnée. Cependant, pour de nombreux problèmes, l'analyse du pire cas ne permet pas de prédire les performances des algorithmes en pratique. En effet, dans de nombreux scénarios, l'entrée est loin d'être le pire cas et présente certaines caractéristiques prévisibles. Les progrès considérables de l'apprentissage automatique et de l'intelligence artificielle au cours des dernières décennies, permettent d'espérer de bonnes prédictions de l'entrée. Cependant, il n'existe aucune garantie formelle sur la qualité d'un prédicteur (d'apprentissage automatique). Notre projet vise à exploiter les données pour traiter l'incertitude (d'entrée) afin de concevoir des algorithmes qui, lorsque la précision des prédictions est bonne, offrent une performance (garantie) proche de celle d'un algorithme qui a un accès complet à l'entrée, et en même temps, lorsque les prédictions sont fausses, offrent une performance qui n'est pas beaucoup plus mauvaise que celle d'un algorithme sans accès aux prédictions.
Dans ce stage, on va se focaliser sur un problème d'ordonnancement et nous allons essayer de concevoir, d'analyser et de tester des algorithmes de résolution prenant en compte de prédictions sur les données.
Bibliographie
https://algorithms-with-predictions.github.io
Evripidis Bampis, Konstantinos Dogeas, Alexander V. Kononov, Giorgio Lucarelli, Fanny Pascual:
Scheduling with Untrusted Predictions. IJCAI 2022: 4581-4587