Un algoritmo per la ricerca approssimativa Steiner Foresta

Question

Si consideri un grafo pesato G = (V, E, w). Ci viene dato una famiglia di sottoinsiemi di vertici V_i.

Uno Steiner Forest è una foresta che per ogni sottoinsieme di vertici V_i collega tutti i vertici in questo sottogruppo con un albero.

Esempio:. Solo un sottoinsieme V_1 = V. In questo caso una foresta Steiner è un albero di copertura dell'intero grafico

Esempio: un P4 grafico (percorso con 4 vertici) e due sottoinsiemi: V_1 = {v1, v4} e {V_2 = v2, v3}. L'albero di Steiner per questo esempio è l'intero grafico.

teoria abbastanza. Trovare tali foresta una con il minimo peso è difficile (NP-completo). Sapete qualsiasi algoritmo più veloce approssimativo di trovare un bosco con un peso non ottimale?

Answer 1

Capitolo 20 di approssimazione Algoritmi da Vijay Vazirani descrive uno schema per la generazione di una foresta Steiner. L'analisi utilizza LP-dualità, che egli utilizza per determinare il fattore dell'algoritmo:

(Questo è un algoritmo di fattore-2, ma in pratica è probabilmente tariffe abbastanza bene)

ravvicinamento Algoritmi

Inoltre: cfr. La nota 22.5, che descrive tre carte per ulteriori letture, tra cui uno studio del tema

Answer 2

Forse si può riformulare questo problema come altri NP-completo, di cui si conosce alcun algoritmi non ottimali? Questa è solo una supposizione, anche se - non riesco a trovare tale mappatura con le mie abilità matematiche molto limitate:)