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

Формально исходными данными обобщенной задачи построения сети Штейнера является неориентированный мультиграф G = (V, E), в котором каждое ребро <math>e \in E \;</math> имеет неотрицательную стоимость cost c(e), а для каждой пары вершин <math>i, j \in V \;</math> имеется требование связности <math>r_{i,j} \in \mathbb{Z} \;</math>. Допустимое решение представляет собой подмножество ребер <math>E' \subseteq E \;</math>, такое, что каждая пара вершин <math>i, j \in V \;</math> соединена по меньшей мере <math>r_{i,j} \;</math> реберно-непересекащихся путей в графе G' = (V, E').

Эта задача обобщает несколько классических задач конструирования сетей. Среди них можно упомянуть минимальное остовное дерево, дереве Штейнера и лес Штейнера. Наиболее общим случаем с ранее известной 2-аппроксимацией была задача построения леса Штейнера [1, 4].

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

Для любого подмножества вершин <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>.

Задача (IP)

8S \subseteq V (1)

eeS(S)

хе€{0,1} Ve € £ (2)

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

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

(3)

0 < xe < 1

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

Задача о создании обобщенной сети Штейнера – очень простая и естественная задача проектирования сетей, имеющая множество вариантов применения в различных областях, включая разработку сетей коммуникаций, проектирование СБИС и маршрутизацию транспорта. Одним из примеров может служить построение сетей коммуникаций с повышенной живучестью, остающихся функциональными даже после отказа некоторых компонентов сети (подробнее см. в [ ]).

Алгоритм 2-аппроксимации Джейна [ ] для обобщенной задачи построения сети Штейнера основан на LP-округлении и имеет достаточно большое время выполнения. Было бы любопытно разработать алгоритм комбинаторной аппроксимации для этой задачи.