Algorithmes avec prédictions – PREDICTIONS

Les algorithmes qui évoluent dans un état d'incertitude occupent une place centrale dans la conception et l'analyse des algorithmes. Alors que les approches traditionnelles sont basées sur l'analyse en l'absence totale d'information, les algorithmes avec prédictions cherchent à exploiter certaines informations intrinsèquement imprécises concernant les parties manquantes de l'entrée. L'objectif est ici de concevoir des algorithmes qui soient robustes aux erreurs de prédiction, tout en étant performants si la prédiction est précise. Les travaux antérieurs réalisés dans ce cadre récent se sont concentrés presque exclusivement sur les prédictions à type unique, déterministes et souvent fournies par des oracles très puissants, sur les techniques basées principalement sur l'analyse concurrentielle du pire cas et sur les problèmes en ligne, dans lesquels l'entrée est révélée sous la forme d'une séquence d'éléments.

Dans ce projet, nous renforcerons et étendrons considérablement les fondations du domaine naissant et en pleine expansion des algorithmes avec prédictions, en abordant tous les aspects du développement d'algorithmes : modélisation, conception, cadre d'analyse théorique et évaluation des performances. Plus précisément, nous proposons trois objectifs principaux. Le premier est l'avancement de nouveaux modèles qui capturent mieux la structure et la sémantique des algorithmes avec prédictions, mais qui se prêtent également à l'analyse théorique. Cela nous aidera à combler le fossé entre des modèles similaires mais fondamentalement différents, et à étudier les algorithmes dans des contextes plus réalistes, mais largement sous-étudiés, tels que les prédictions stochastiques et multiples. Notre deuxième objectif est de rechercher de nouvelles techniques d'analyse qui reflètent mieux la puissance et les limites des algorithmes avec prédictions. Cela nous permettra d'obtenir une évaluation plus nuancée au-delà des considérations du "pire cas", de mieux comprendre l'impact de l'erreur de prédiction sur la performance des algorithmes et d'exploiter des techniques inexplorées basées sur l'optimisation continue. Notre troisième objectif est d'introduire et d'exploiter les concepts de prédiction dans des contextes qui vont au-delà de l'informatique en ligne, notamment dans l'informatique distribuée et le parallélisme, dans les algorithmes de streaming et d'approximation (hors ligne), ainsi que dans les aspects algorithmiques des jeux de recherche. Cela nous aidera à transférer les outils et l'expertise mathématiques à des domaines dans lesquels les prédictions peuvent être bénéfiques, mais où très peu de travaux antérieurs (voire aucun) ont abordé de telles connexions. Notre objectif final est de saisir et d'analyser efficacement des paramètres réalistes qui se produisent souvent dans des domaines pratiques, dans le contexte de problèmes et d'applications bien connus.