Обобщенная задача построения сети Штейнера: различия между версиями

Уильямсон и др. [8] первыми представили нетривиальный алгоритм аппроксимации для обобщенной задачи построения сети Штейнера, получив 2k-аппроксимацию, где <math>k = max_{i,j \in V} \{ r_{i, j} \} \;</math>. Этот результат был улучшен до O(log k)-аппроксимации в работе Геманса и др. [3].

Алгоритм аппроксимации использует технику LP-округления. Исходная линейная программа (LP) получается из программы (IP) в результате замены ограничения целочисленности (2) на ограничение

Алгоритм аппроксимации выполняет итеративное LP-округление. Пусть имеется базовое оптимальное решение (LP); обозначим за <math>E^* \subseteq E \;</math> подмножество ребер e с <math>x_e \ge 1/2 \;</math>. Ребра из E* удаляются из графа (и затем добавляются к решению), после чего задача рекурсивно решается на оставшемся графе при помощи решения (LP) на G* = (V, E \ E*), где для каждого подмножества <math>S \subseteq V \;</math> имеется новое требование <math>f(S) - | \beta (S) \cap E^* | \;</math>. Следующее наблюдение приводит к получению аппроксимации с коэффициентом 2: если E' является 2-аппроксимацией для оставшейся задачи, то <math>E' \cap E^* \;</math> является 2-аппроксимацией для исходной задачи.