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

Формально исходными данными обобщенной задачи построения сети Штейнера является неориентированный мультиграф 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>.

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

Алгоритм аппроксимации выполняет итеративное LP-округление. Пусть имеется базовое оптимальное решение (LP); обозначим за <math>E^* \subseteq E \;</math> подмножество ребер e с <math>x_e \ge 1/2 \;</math>. Ребра из E* удаляются из графа (и затем добавляются к решению), после чего задача рекурсивно решается на оставшемся графе при помощи решения (LP) на G* = (V, E \ E*), где для каждого подмножества <math>S \subseteq V \;</math> имеется новое требование <math>f(S) - | \beta (S) \cap E^* | \;</math>. Следующее наблюдение приводит к получению аппроксимации с коэффициентом 2: если E' является 2-аппроксимацией для оставшейся задачи, то <math>E' \cap E^* \;</math> является 2-аппроксимацией для исходной задачи.

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

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