Nouvelles Techniques en Calcul en-ligne – NeTOC

L'algorithmique en ligne est un domaine de l'informatique très actif et bien établi. Il concerne la conception et l'analyse d'algorithmes qui opèrent dans un contexte où les données sont fournies au fur et à mesure à l'algorithme. Celui-ci doit néanmoins effectuer des actions à chaque nouvelle réception de données. La problématique centrale vient du fait que l'algorithme en ligne ne connait pas les réceptions futures. Depuis l'introduction de l'analyse compétitive par Sleator et Tarjan en 1985, une large palette de problèmes ont été étudiés sous cet angle, et de nombreux résultats importants ont été obtenus.

Cette activité de recherche massive et fructueuse a cependant montré des faiblesses. D'une part le modèle repose sur l'hypothèse que l'algorithme en ligne n'a aucune idée des données futures, alors que dans certains cas, une certaine information sur le futur est présente. Et d'autre part, l'analyse compétitive compare les algorithmes en ligne au concept d'un algorithme hors ligne, clairvoyant, et tout puissant qui connaîtrait tout le futur en avance. La comparaison avec un algorithme aussi puissant donne lieu parfois à une classification trop grossière qui n'arrive pas à faire la part des algorithmes en ligne qui ont clairement des comportement nettement différent en pratique.

Dans cette demande de financement, nous répondons à ces faiblesses par des nouvelles technique que nous avons introduits récemment. Plus précisément, nous nous proposons d'étudier le rapport qu'il peut y avoir entre l'information sur les données futures et le ratio de compétitivité, en utilisant notre modèle d'algorithme en ligne avec conseil. De plus nous comptons étudier les performances relatives de différents algorithmes en ligne se basant sur notre méthode n'analyse bijective. Ensuite nous envisageons de combiner ces deux techniques afin d'obtenir de nouvelles connaissances dans le domaine de l'algorithmique en ligne.

Obtenir de nouveaux résultats spécifiques en calcul en-ligne est un but, mais un des objectifs de ce projet est aussi de se rendre compte des domaines d'applications et de l'utilité des nouvelles techniques que nous avons introduits ces dernières années. Nous comptons les affiner, si possible les combiner, et prouver leur utilité dans un rayon plus large. Donc un de nos objectifs principaux est de construire une fondation solide pour ces techniques, qui trouveront résonance dans le domaine.