logo EDITE Sujets de doctorat

Algorithmes en ligne avec re-optimisation

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Shendan JIN
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

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~\citeBorodinEl-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.

Enjeux

La programmation linéaire a été utilisée comme un outil unificateur de conception et d'analyse d'algorithmes d'approximation pour des problèmes combinatoires (en anglais primal dual approximation schemes). Cette technique est très bien comprise et enseignée depuis des dizaines d'années, voir~\citeVazirani:13:Approximation-algorithms. Plus récemment cette démarche a également portée ses fruits dans le domaine de l'algorithmique en ligne, et est bien décrite dans l'ouvrage \citeBuchbinderNaor:09:The-design-of-competitive. Elle permet par exemple d'expliquer et d'améliorer d'une manière simple l'algorithme décrit dans \citeAspnesAzar:93:On-line-load pour le problème de maximisation de demandes de connexions acceptés, dans le modèle d'un graphe aux capacités statiques et où les routes ne peuvent pas être changées, voir \citeBuchbinderNaor:06:Improved-bounds.

Récemment la possibilité de revenir sur ses décisions dans un algorithme en ligne a été explorée. Il y a d'abord un travail fondateur sur le problème générique de \emphset packing (entre autres), qui autorise à enlever un ensemble de la solution \citeAvitabileMathieu:13:Online-constrained. Le problème consiste en un univers, et une collection d'ensembles de taille et de poids différents et le but est de produire une collection d'ensembles disjoints de poids total maximum. Dans \citeAvitabileMathieu:13:Online-constrained une variable de décision (sélection d'un ensemble dans la solution) peut changer un nombre constant de fois.

Un autre travail étudie le problème de l'arbre de recouvrement minimum où les sommets arrivent en ligne et à tout moment un nombre constant d'arêtes peuvent être changées dans la solution.

Dans le problème d'arbre de Steiner en ligne, les sommets terminaux arrivent au fur et à mesure dans un espace métrique, et il faut les connecter immédiatement à l'arbre courant par un chemin de votre choix, en tentant de minimiser la longueur totale de l'arbre. Depuis deux décennies on sait que l'algorithme glouton est $O(\log n)$ – où $n$ est le nombre de sommets terminaux — et que ceci est optimal. Mais imaginons que dans un contexte de re-optimisation, l’algorithme a la possibilité de changer un chemin existant, avec chaque nouveau chemin ajouté à l'arbre. Est-ce que le ratio de compétitivité peut alors être amélioré~? En effet, Megow, Skutella et Verschae \citeMegowSkutella:12:The-power-of-recourse ont récemment montré que le ratio devient alors constant. Dans leur algorithme par contre le nombre de changement par requête était seulement constant au sens amorti. Cette restriction a été enlevée par Gu, Gupta and Kumar~\citeGuGupta:16:The-Power-of-Deferral: avec un algorithme primal dual, et une nouvelle technique d'analyse.

Dans cette thèse nous voudrions poursuivre cette direction fructueuse et étudier d'autres variantes d'arbres de Steiner. En particulier le cas d'une métrique de graphe \emphorienté, le cas pondéré sur les sommets et les arbres de Steiner avec priorité. Toutes ces variantes ont comme point commun qu'ils sont extrêmement difficile et que le meilleur ratio de compétitivité est $O(n)$ — atteint par des algorithmes complètement naïfs — qui contraste avec le ratio $O(\log n)$ du problème standard. Étudier ces problèmes dans le contexte de la re-optimisation permettra de produire des algorithmes plus performants et plus intéressants. Les encadrants ont une bonne expérience sur d'autres approches à ces questions, voir \citeAngelopoulos:09:Online-Priority,Angelopoulos:08:A-Near-Tight-Bound,Angelopoulos:07:Improved-bounds,Angelopoulos:06:The-Node-Weighted-Steiner.

Ouverture à l'international

Le travail de la thèse reposera sur une compréhension profonde de l'approche primale-duale dans l'algorithmique en ligne et exploitera les particularités combinatoires de chacun des problèmes étudiés. Une direction qui n'a pas encore été explorée, est d'incorporer des technique de mise à jour paresseuse des structures de données (par exemple dans les arbres de segment) dans un algorithme en ligne avec re-optimisation.

Pour les publications on ciblera les conférences comme ESA, SODA, ICALP, STACS et MFCS. Le thésard sera aussi en contact étroit avec les collaborateurs des encadrants et pourra, on espère, passer des séjours de recherche chez eux. Ces contacts incluent Chien-Chung Huang (Göteburg), Nikhil Bansal (Eindhoven), José Verschae (Santiago de Chile) et Nicole Megow (Munich), Marek Chrobak (Riverside) et Dimitris Fotakis (Athènes).

Remarques additionnelles

La thèse débutera par une mise à niveau dans le domaine de l'algorithmique en ligne, et une bibliographie sur les travaux récents cités ci-haut. Puis le problème de routage en ligne avec possibilité de re-routage sera étudié. Ici trois modèles pourront être considérées~: maximisation du nombre de requêtes acceptées avec limite constant sur le nombre de re-routage, le même modèle avec une limite amortie, et le modèle avec maximization d'un profit engendré par les requêtes acceptées (somme des poids) moins le coût généré par les re-routages.

Pour clore la thèse, l'impact des techniques développées serait mesuré en les appliquant à différents problèmes classiques en optimisation combinatoire.