Algorithmique en ligne au delà des approches traditionnelles – OATA

Traditionnellement, la conception et l'analyse d'algorithmes supposent qu'un algorithme a la connaissance parfaite et complète sur des données. Cependant, dans de nombreux contextes, les données sont révélées en ligne au fil du temps sous forme des requêtes, et l'algorithme a besoin de prendre des décisions irrévocables sans la connaissance du futur. Tels contextes apparaissent dans plusieurs situations, de l'ordonnancement des tâches en ligne, la gestion du portefeuille des actions à la prédiction de la météo, etc. Ainsi, la question principale dans l'algorithmique en ligne est d'obtenir de bonnes performances dans un contexte d'incertitude due aux données arrivant séquentiellement. En outre, l'émergence des problèmes de données massives nécessite des algorithmes qui résolvent les problèmes avec un seul passage sur les données dans le sens de l'algorithmique en ligne.

L'algorithmique en ligne est un domaine actif et bien établi. De nombreux algorithmes intéressants avec performance garantie, de nombreuses techniques profondes ont été conçus. Toutefois, l'ensemble actuel des techniques ne fournit pas de moyens efficaces pour étudier les problèmes dans lesquels la nature est non-linéaire ou bien non-convexe comme la minimisation de l'énergie en optimisation combinatoire ou l'optimisation des fonctions sous-modulaires en apprentissage. Le développement des nouvelles méthodes est crucial pour l'avancement du domaine.

L'autre aspect principal, bien identifié en l'algorithmique en ligne, est la faiblesse de l'analyse du pire des cas. Résumer le comportement d'un algorithme en se basant sur une instance pathologique ne reflète pas nécessairement sa performance. De nombreux algorithmes comportant très bien en pratique admettent paradoxalement une garantie théorique médiocre et vice versa. Plusieurs modèles ont été introduits avec le but de donner des mesures plus précises sur les algorithmes au-delà de l'analyse du pire des cas. Chaque modèle réussit à expliquer les performances des algorithmes dans certains contextes, mais rencontre des difficultés dans d'autres. Un point commun de ces modèles est qu'ils ne possèdent pas d'outil approprié et en général utilisent les mêmes outils comme dans l'analyse du pire des cas. L'absence d'outils appropriés est un obstacle majeur pour le développement de ces modèles.

Dans le projet, notre premier objectif est d'établir de nouvelles méthodes pour la conception et l'analyse d'algorithmes en ligne au-delà des techniques actuelles. Nous visons à développer des approches pour étudier les problèmes convexes et non convexes. Le deuxième objectif est d'étudier de nouveaux modèles mesurant précisément les performances des algorithmes au delà de l'analyse du pire cas. En particulier, nous sommes intéressés à la fondation d'un modèle général de l'augmentation des ressources unifié des modèles précédents qui semblent non-reliés. Afin de réaliser ces deux objectifs, nous proposons de nouvelles approches basées sur le paradigme de la dualité de la programmation mathématique comme un outil traversal.

A côté des intérêts théoriques, l'avancement du projet apporterait des idées et des améliorations dans la conception d'algorithmes de manière significative dans le domaine du développement durable (par exemple, la minimisation d'énergie en ordonnancement) et dans le contexte des données massives (par exemple, l'optimisation des fonctions sous-modulaires).