Versions "bottleneck" de problèmes classiques d'optimisation.

De nombreux problèmes de graphes pondérés consistent à trouver des sous-structures S optimisant la fonction  Σ_{s ∈ S} poids(s) (autrement dit on cherche  son maximum ou bien son minimum quand S parcourt l'ensemble des sous-structures). C'est par exemple le cas des problèmes suivants :

• plus court chemin entre deux sommets x et y où on cherche à minimiser Σ_{1 ≤i<k} poids(x_ix_i+1) pour tous les chemins (x=x₁,x₂,...,x_k=y),
  
• arbre couvrant de poids minimum où l'on cherche à minimiser Σ_{xy arête de T} poids(xy) pour tous les arbres couvrants T,
  
• ensemble de sommets de poids minimum couvrant les arêtes où on veut minimiser Σ_{s ∈ S} poids(s) pour tous les ensembles S de sommets couvrants toutes les arêtes (version pondérée de Vertex Cover).

Tous ces problèmes admettent des variantes, appelées "bottleneck" (goulot), qui consistent à remplacer le Σ par un min ou bien un max. Par exemple, les trois problèmes cités au-dessus peuvent être repris en remplaçant le Σ par un max, et en gardant comme objectif de minimiser la fonction par rapport à toutes les sous-structures considérées dans chaque cas. Ces variantes peuvent avoir du sens pour certaines applications. Par exemple, ayant un réseau de communication à disposition, on souhaite échanger les messages à travers un sous-réseau qui sera un arbre couvrant. Supposons que les poids sur les arêtes indiquent des capacités (comme des débits offerts) et que les messages échangés sur un chemin entre deux sommets sont limités par la plus petite capacité sur le chemin (effet "goulot d'étranglement"), alors l'optimisation de performance pour toute paire de sommets peut se ramener à chercher un arbre couvrant qui maximise le poids minimum de ses arêtes (noter que c'est l'inverse de la version proposée au-dessus).

L'objectif ici est de comparer la complexité des versions classiques avec leurs versions "bottleneck". En l'illustrant sur des exemples (comme les trois du dessus), montrer que souvent la version "bottleneck" d'un problème est plus facile à résoudre que la version initiale avec somme des poids (je ne sais pas si on pourrait en faire un genre de méta-théorème avec un argument solide ?).

optimiser (ici minimiser)	version classique avec Σ	version bottleneck avec max
chemin entre deux sommets
arbre couvrant les sommets
ensemble de sommets couvrant les arêtes
autres idées d'exemples ...

Quelques références (pas exhaustif).

• Un partiel de graphes, avec en question 4, une étude de la version "bottleneck" des arbres couvrants : ses liens avec les arbres couvrants de poids minimum  (où le poids est la somme) et des indications pour mettre en place un algorithme efficace de calcul.
• Introduction to Algorithms, livre de T. Cormen, C. Leiserson, R. Rivest (et C. Stein dans la dernière édition), MIT Press (2001) (traduit en français: Introduction à l'algorithmique, chez Dunod).

Retour à la page des sujets.