Un algorithme approximatif pour trouver la forêt de Steiner

Question

Considérons un graphe pondéré G = (V, E, w). On nous donne une famille de sous-ensembles de sommets V_i. Une forêt de Steiner est une forêt qui, pour chaque sous-ensemble de sommets, relie tous les sommets de ce sous-ensemble à un arbre. Exemple: un seul sous-ensemble V_1 = V. Dans ce cas, une forêt de Steiner est un arbre couvrant de tout le graphe. Exemple: un graphe P4 (chemin avec 4 sommets) et deux sous-ensembles: V_1 = {v1, v4} et V_2 = {v2, v3}. L'arbre de Steiner pour cet exemple est le graphique entier.

Enough theory. Trouver une telle forêt avec un poids minimal est difficile (NP-complet). Connaissez-vous un algorithme approximatif plus rapide pour trouver une telle forêt avec un poids non-optimal?

Answer 1

Chapitre 20 de l'approximation des algorithmes par Vijay Vazirani décrit un schéma pour générer une forêt Steiner. L'analyse utilise LP-dualité, qu'il utilise pour déterminer le facteur de l'algorithme:

(Ceci est un facteur-2 algorithme, mais en pratique, il probablement des tarifs très bien)

Approximation Algorithms

également: voir la note de 22.5 qui décrit trois articles à lire, y compris un aperçu du sujet.

Answer 2

Peut-être pouvez-vous répéter ce problème comme NP-complet, pour lequel vous connaissez des algorithmes sous-optimaux? Ceci est juste une supposition, mais - je ne peux pas trouver une telle cartographie avec mes compétences très limitées en mathématiques :)