Une approche unifiée des algorithmes d'approximation pour les problèmes de goulot d'étranglement

Dans cet article, une technique puissante, et pourtant simple, pour concevoir des algorithmes d'approximation pour une grande variété de problèmes NP-complets en routage, localisation et conception de réseaux de communication est étudiée. Chacun des algorithmes présentés ici fournit une solution approximative garantie d'être à un facteur constant de la solution optimale. De plus, pour plusieurs de ces problèmes, nous pouvons montrer que, sauf si P = NP, il n'existe pas d'algorithme en temps polynomial ayant une meilleure garantie de performance.