Обобщенная задача построения сети Штейнера
Ключевые слова и синонимы
Построение сети с повышенной живучестью
Постановка задачи
Обобщенная задача построения сети Штейнера получает на входе граф и набор требований связности и пытается найти самый недорогой подграф, удовлетворяющий этим требованиям.
Формально исходными данными обобщенной задачи построения сети Штейнера является неориентированный мультиграф G = (V, E), в котором каждое ребро [math]\displaystyle{ e \in E \; }[/math] имеет неотрицательную стоимость c(e), а для каждой пары вершин [math]\displaystyle{ i, j \in V \; }[/math] имеется требование связности [math]\displaystyle{ r_{i,j} \in \mathbb{Z} \; }[/math]. Допустимое решение представляет собой подмножество ребер [math]\displaystyle{ E' \subseteq E \; }[/math], такое, что каждая пара вершин [math]\displaystyle{ i, j \in V \; }[/math] соединена по меньшей мере [math]\displaystyle{ r_{i,j} \; }[/math] реберно-непересекащихся путей в графе G' = (V, E').
Обобщенная задача построения сети Штейнера заключается в нахождении решения E' с минимальной стоимостью [math]\displaystyle{ \sum_{e \in E'} c(e) \; }[/math].
Эта задача обобщает несколько классических задач конструирования сетей. Среди них можно упомянуть минимальное остовное дерево, дерево Штейнера и лес Штейнера. Наиболее общим случаем с ранее известной 2-аппроксимацией была задача построения леса Штейнера [1, 4].
Уильямсон и др. [8] первыми представили нетривиальный алгоритм аппроксимации для обобщенной задачи построения сети Штейнера, получив 2k-аппроксимацию, где [math]\displaystyle{ k = max_{i,j \in V} \{ r_{i, j} \} \; }[/math]. Этот результат был улучшен до O(log k)-аппроксимации в работе Геманса и др. [3].
Основные результаты
Основным результатом работы [6] стал алгоритм 2-аппроксимации для обобщенной задачи построения сети Штейнера. Техника, использованная для разработки и анализа алгоритма, представляет отдельный интерес.
2-аппроксимация получена для более общей задачи, которая формулируется следующим образом. Пусть имеется мультиграф G = (V, E) с ребрами стоимостью [math]\displaystyle{ c( \cdot ) \; }[/math] и функция требований связности [math]\displaystyle{ f: 2^V \to \mathbb{Z} \; }[/math]. Функция f является слабо субмодулярной, т.е. имеет следующие свойства:
1. f(V) = 0.
2. Для любых [math]\displaystyle{ A, B \subseteq V \; }[/math] выполняется по меньшей мере одно из двух следующих условий:
[math]\displaystyle{ f(A) + f(B) \le f(A \backslash B) + f(B \backslash A) \; }[/math];
[math]\displaystyle{ f(A) + f(B) \le f(A \cap B) + f(A \cup B) }[/math].
Для любого подмножества вершин [math]\displaystyle{ S \subseteq V \; }[/math] обозначим за [math]\displaystyle{ \delta (S) \; }[/math] множество ребер, строго одна из конечных точек которых принадлежит к S. Задача заключается в нахождении подмножества ребер минимальной стоимости [math]\displaystyle{ E' \subseteq E \; }[/math], такого, что для любого подмножества вершин [math]\displaystyle{ S \subseteq V }[/math] выполнялось бы свойство [math]\displaystyle{ | \delta (S) \cap E' | \ge f(S) \; }[/math].
Задачу можно эквивалентно представить в виде целочисленной программы. Для каждого ребра [math]\displaystyle{ e \in E \; }[/math] обозначим за [math]\displaystyle{ x_e \; }[/math] индикаторную переменную, обозначающую, принадлежит ли ребро e к решению.
Задача (IP)
Найти [math]\displaystyle{ min \sum_{e \in E} c(e) x_e \; }[/math]
при условиях
(1) [math]\displaystyle{ \sum_{e \in \delta (S)} x_e \ge f(s) \; \; \; \forall S \subseteq V }[/math]
(2) [math]\displaystyle{ x_e \in \{ 0, 1 \} \; \; \; \forall e \in E }[/math]
Легко увидеть, что обобщенная сеть Штейнера представляет собой специальный случай задачи (IP), где для каждого [math]\displaystyle{ S \subseteq V \; }[/math] верно [math]\displaystyle{ f(S) = max_{i \in S, j \notin S} \{ r_{i, j} \} \; }[/math].
Техника
Алгоритм аппроксимации использует технику LP-округления. Исходная линейная программа (LP) получается из программы (IP) в результате замены ограничения целочисленности (2) на ограничение
(3) [math]\displaystyle{ 0 \le x_e \le 1 \; \; \; \forall e \in E }[/math]
Предполагается, что имеется оракул разделения для (LP). Легко увидеть, что такой оракул существует, если (LP) получено из обобщенной задачи построения сети Штейнера. Главный результат, использовавшийся в процессе разработки и анализа алгоритма, представлен в следующей теореме.
Теорема 1. В любом базовом решении задачи (LP) имеется по меньшей мере одно ребро [math]\displaystyle{ e \in E \; }[/math] с [math]\displaystyle{ x_e \ge 1/2 \; }[/math].
Алгоритм аппроксимации выполняет итеративное LP-округление. Пусть имеется базовое оптимальное решение (LP); обозначим за [math]\displaystyle{ E^* \subseteq E \; }[/math] подмножество ребер e с [math]\displaystyle{ x_e \ge 1/2 \; }[/math]. Ребра из E* удаляются из графа (и затем добавляются к решению), после чего задача рекурсивно решается на оставшемся графе при помощи решения (LP) на G* = (V, E \ E*), где для каждого подмножества [math]\displaystyle{ S \subseteq V \; }[/math] имеется новое требование [math]\displaystyle{ f(S) - | \beta (S) \cap E^* | \; }[/math]. Следующее наблюдение приводит к получению аппроксимации с коэффициентом 2: если E' является 2-аппроксимацией для оставшейся задачи, то [math]\displaystyle{ E' \cap E^* \; }[/math] является 2-аппроксимацией для исходной задачи.
Пусть дано любое решение (LP). Множество [math]\displaystyle{ S \subseteq V \; }[/math] называется плотным в том и только том случае, если ограничение (1) удовлетворяется для S в виде равенства. Доказательство теоремы 1 включает построение большого ламинарного семейства плотных множеств (семейства, в котором для любой пары множеств либо одно множество содержит другое, либо множества не пересекаются). После этого применяется продуманная схема учета, которая назначает ребра множествам ламинарного семейства, чтобы показать, что существует по меньшей мере одно ребро [math]\displaystyle{ e \in E \; }[/math] с [math]\displaystyle{ x_e \ge 1/2 \; }[/math].
Применение
Задача о создании обобщенной сети Штейнера – очень простая и естественная задача проектирования сетей, имеющая множество вариантов применения в различных областях, включая разработку сетей коммуникаций, проектирование СБИС и маршрутизацию транспорта. Одним из примеров может служить построение сетей коммуникаций с повышенной живучестью, остающихся функциональными даже после отказа некоторых компонентов сети (подробнее см. в [5]).
Открытые вопросы
Алгоритм 2-аппроксимации Джейна [6] для обобщенной задачи построения сети Штейнера основан на LP-округлении и имеет достаточно большое время выполнения. Было бы любопытно разработать алгоритм комбинаторной аппроксимации для этой задачи.
Пока неизвестно, возможна ли лучшая аппроксимация для обобщенной задачи построения сети Штейнера. Для этого типа задач известно очень мало результатов сложности аппроксимации. Пока что наилучший известный коэффициент сложности составляет 1,01063 [2]; этот результат действителен и для специального случая дерева Штейнера.
См. также
Литература
1. Agrawal A., Klein P., Ravi R.: When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. J. SIAM Comput. 24(3), 440^56 (1995)
2. Chlebik M., Chlebikova J.: Approximation Hardness of the Steiner Tree Problem on Graphs. In: 8th Scandinavian Workshop on Algorithm Theory. Number 2368 in LNCS, pp. 170-179, (2002)
3. Goemans M.X., Goldberg A.V., Plotkin S.A., Shmoys D.B., Tardos Ё., Williamson D.P.: Improved Approximation Algorithms for Network Design Problems. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 223-232.(1994)
4. Goemans M.X., Williamson D.P.: A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput. 24(2), 296-317(1995)
5. Grotschel M., Monma C.L., Stoer M.: Design of Survivable Networks. In: Network Models, Handbooks in Operations Research and Management Science. North Holland Press, Amsterdam, (1995)
6. Jain K.: A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. Combinatorica 21(1), 39-60 (2001)
7. Vazirani V.V.: Approximation Algorithms. Springer, Berlin (2001)
8. Williamson D.P., Goemans M.X., Mihail M., Vazirani V.V.: A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. Combinatorica 15(3),435-454 (1995)