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

Для любого подмножества вершин S С V обозначим за 8(S) множество ребер, строго одна из конечных точек которых принадлежит к S. Задача заключается в нахождении подмножества ребер минимальной стоимости E0 С E, такого, что для любого подмножества вершин S С V верно \S(S) \ E'\ > f(S). (IP)

Задачу можно эквивалентно представить в виде целочисленной программы. Для каждого ребра e 2 E обозначим за xe индикаторную переменную, обозначающую, принадлежит ли ребро e к решению.

8S С V (1)

Легко увидеть, что обобщенная сеть Штейнера представляет собой специальный случай задачи (IP), где для каждого S С V выполняется f(S) = maxi2S;j26Sfri;jg.

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

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