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

Алгоритм аппроксимации выполняет итеративное LP-округление. Пусть имеется базовое оптимальное решение (LP); обозначим за E* \subseteq E подмножество ребер e с xe > 1/2. Ребра из E* удаляются из графа (и затем добавляются к решению), после чего задача рекурсивно решается на оставшемся графе за счет решения (LP) на G* = (V, En Ј*), где для каждого подмножества S \subseteq V имеется новое требование f(S) — \S(S) \ E* j. Следующее наблюдение приводит к получению аппроксимации с коэффициентом 2: если E0 является 2-аппроксимацией для оставшейся задачи, то E0 [ E* является 2-аппроксимацией для исходной задачи.

Пусть дано любое решение (LP). Множество S \subseteq V называется плотным в том и только том случае, если ограничение (1) удовлетворяется для S в виде равенства. Доказательство теоремы 1 включает построение большого ламинарного семейства плотных множеств (семейства, в котором для любой пары множеств либо одно множество содержит другое, либо множества не пересекаются). После этого применяется продуманная схема учета, которая назначает ребра множествам ламинарного семейства, чтобы показать, что существует по меньшей мере одно ребро e 2 E с xe > 1/2.