Algorithmes avec Prédictions

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 projet, on va se focaliser sur un problème d'optimisation (problème d'ordonnancement ou de graphes) et nous allons essayer de concevoir et de tester des algorithmes de résolution prenant en compte de prédictions sur les données.