Description
Date depot: 1 janvier 1900
Titre: Algorithmes en ligne avec re-optimisation
Directeur de thèse:
Spyros ANGELOPOULOS (LIP6)
Directeur de thèse:
Christoph DURR (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Le but de la thèse est de développer des algorithmes en ligne dans le modèle où l'algorithme peut revenir sur ses décisions moyennant un coût (re-optimisation, ou en anglais {recourse actions}). En particulier nous souhaitons travailler sur le problème d'acceptation de demandes de connections dans un réseau à capacité limité (en anglais {online routing} ou {admission control}), ainsi que des variantes du problème de Steiner. L'algorithmique en ligne dispose d'un outil puissant, l'approche primale-duale, qui permet d'analyser et de concevoir de manière systématique des algorithmes en ligne. La thèse s'efforcera d'étendre cette technique à des modèles avec re-optimisation.
Le principe des algorithmes en ligne consiste à ce que l'entrée ne soit pas donnée au programme d'un coup mais sous forme d'une séquence de requêtes. Chaque requête doit être servie par une action, qui est irréversible et qui entraîne un coût. Le but est de produire une solution dont le coût serait aussi proche que possible du coup optimal qu'on aurait pu calculer si on avait eu connaissance de l'entrée complète dés le début. Un exemple classique est par exemple le routage dans un graphe doté de capacités sur les arêtes, où les requêtes représentent des couples de sommets à relier, et il faut choisir un chemin utilisant des arêtes pas encore saturées. Le but est de servir le plus de requêtes possibles, voir~cite{BorodinEl-Yaniv:05:Online-computation}.
Il y a des situations dans lesquels il est possible de revenir sur ces décisions, dans l'exemple cité il est par exemple possible de re-router certaines connections, pour créer de la capacité dans une partie du graphe. Ces opérations ont un coût, et il est alors possible de l'ajouter dans la fonction objective ou de le considérer comme une contrainte, par exemple en autorisant un seul re-routage par requête. Un premier travail a été fait pour intégrer cette possibilité dans la technique d'analyse par programmation linéaire, qui a posé une contrainte sur le nombre de modifications. La thèse tenterait alors d'explorer la possibilité d'intégrer cette mesure dans la valeur objective pour être au plus proche des applications.
Le problème cité nous a été communiqué par la société Huawei, opérateur de télécommunication, qui dispose de réseaux permettant d'avoir une vue globale des congestions et donnant la possibilité de changer de routes pour certaines connexions.
Nous allons également aborder des variantes du problème d'arbre de Steiner, qui est central pour la conception d'un réseau d'interconnexion.
Développer des algorithmes en ligne avec re-optimisation permet de répondre à de nouvelles applications et combiner des techniques d'algorithmes en ligne avec ceux des structures de données dynamiques.
Doctorant.e: Jin Shendan