Autour de l'approximabilité du problème de dimensionnement robuste des réseaux

Le probleme de dimensionnement robuste d'un reseau consistea choisir les capacites des liens en minimisant un certain cout lineaire et en prenant en compte l'incertitude de la matrice de trafic. Pour modeliser cette incertitude duea la dynamicite de la demande eta la difficulte de la mesurer et de la predire, nous faisons l'hypothese que la matrice de trafic varie dans un ensemble polyedrique donne. L'objectif est alors de choisir un vecteur de capacites de cout minimum de telle sorte que chaque matrice de trafic du polyedre soit routable sur ces capacites. Le routage est supposeetre dynamique, c'esta dire qu'il varie avec la matrice de trafic. On supposeegalement que le routage est fractionnaire. [Che07] a decrit un algorithme polynomial pour resoudre ce probleme d'une maniere approchee avec un rapport d'approximation de O(log n). Il a aussiete demontre que ce probleme est co-NP-difficile dans les cas oriente [GKK + 01] et non oriente [CSOS07]. En utilisant seulement la conjecture P = NP, nous montrons dans cet article que ce probleme est inapproximable avec un rapport d'approximation en dessous d'un certain facteur constant.