Doktorarbeit,
Algorithmique et télécommunications : coloration et multiflot approchés et applications aux réseaux d'infrastructure
Université de Nice-Sophia Antipolis, (November 2003)
Zusammenfassung
Cette thèse s'intéresse aux problématiques fondamentales
d'optimisation combinatoire qui se dégagent de la modélisation
structurelle et algorithmique du dimensionnement des réseaux
d'infrastructure de télécommunication. L'optimisation de ces réseaux
est essentielle aux opérateurs de télécommunication, qui demandent la
garantie d'une exploitation efficace des ressources déployées. Nous
donnons une nouvelle modélisation des réseaux optiques WDM
multifibres. En considérant un routage agrégé au niveau des c‚bles,
nous optons pour une nouvelle lecture des contraintes d'affectation
de longueurs d'onde fondée sur des conflits de groupe. Nous étudions
aussi le problème de coloration de chemins, issu de l'affectation de
longueurs d'onde dans les réseaux optiques monofibres. Nous
développons, pour la relaxation linéaire de ce problème, un
algorithme polynomial efficace dans les arbres de degré borné, puis,
par extension, dans les graphes de largeur arborescente bornée. Nous
majorons le co˚t d'une telle coloration dans les arbres binaires et
donnons une (1+5/(3e)+o(1))-approximation aléatoire pour la
coloration entière dans les arbres de degré borné, ce qui améliore le
meilleur algorithme connu pour ce cas. Nous présentons enfin des
avancées algorithmiques pour les problèmes de multiflot entier et
fractionnaire. Nous donnons un algorithme d'arrondi aléatoire
incrémental pour l'approximation du multiflot entier. Motivés par le
besoin d'un calcul rapide de multiflot fractionnaire pour
l'algorithme précédent, nous nous intéressons aux approximations
combinatoires de ce problème. En employant des techniques de calcul
dynamique des plus courts chemins, nous améliorons l'un des meilleurs
algorithme de la littérature.
