Примерный алгоритм поиска Штейнер Форест

Question

Рассмотрим взвешенный граф G = (V, E, w). Нам дано семейство подмножеств вершин V_i.

Лес Штейнера - это лес, который для каждого подмножества вершин V_i соединяет все вершины этого подмножества с деревом.

Пример: только одно подмножество V_1 = V. В этом случае лес Штейнера является остовным деревом всего графа.

Пример: граф P4 (путь с 4 вершинами) и два подмножества: V_1 = {v1, v4} и V_2 = {v2, v3}. Дерево Штейнера для этого примера - это весь граф.

Достаточно теории. Найти такой лес с минимальным весом сложно (NP-полная). Знаете ли вы какой-нибудь более быстрый приблизительный алгоритм поиска такого леса с неоптимальным весом?

Answer 1

Глава 20 алгоритмов аппроксимации Виджей Вазирани описывает схему генерации леса Штейнера. В анализе используется LP-двойственность, которую он использует для определения фактора алгоритма:

(Это алгоритм с коэффициентом 2, но на практике он, вероятно, работает довольно хорошо)

Алгоритмы аппроксимации

Также: см. Примечание в 22.5, в котором описаны три статьи для дальнейшего чтения, включая обзор темы.

Answer 2

Может быть, вы можете переформулировать эту проблему как другую NP-полную, для которой вы знаете какие-то неоптимальные алгоритмы? Это всего лишь предположение - я не могу найти такое отображение с моими очень ограниченными математическими навыками:)