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

Перейти к навигации Перейти к поиску
Строка 32: Строка 32:




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




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


при условии:
Задача (IP)


8S С V (1)
Найти <math>min \sum_{e \in E} c(e) x_e \;</math>
 
при условиях
 
8S \subseteq V (1)
eeS(S)
eeS(S)
хе€{0,1} Ve € £ (2)
хе€{0,1} Ve € £ (2)




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




Строка 60: Строка 64:




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


== Применение ==
== Применение ==
4431

правка

Навигация