Лес Штейнера
Ключевые слова и синонимы
Присоединение по требованию; R-присоединение
Постановка задачи
Построение леса Штейнера представляет собой фундаментальную задачу проектирования сетей. Говоря неформально, цель заключается в установлении соединений между парами вершин данной сети по минимальной стоимости. Это обобщение широко известной задачи построения дерева Штейнера. К примеру, предположим, что телекоммуникационная компания получает от своих клиентов запросы на коммуникации. Каждому клиенту требуется соединение между двумя вершинами в данной сети. Задача компании заключается в построении сетевой инфраструктуры с минимальной стоимостью, удовлетворяющей всем запросам на коммуникации.
Формальное определение и нотация
Экземпляр задачи построения леса Штейнера I = (G, c, R) составляют неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E, неотрицательная стоимостная функция [math]\displaystyle{ c: E \to \mathbb{Q}^+ \; }[/math] и множество пар вершин [math]\displaystyle{ R = \{ (s_1, t_1 ), ..., (s_k, t_k) \} \subseteq V \times V \; }[/math]. Пары в множестве R называются парами полюсов. Допустимое решение задачи представляет собой подмножество [math]\displaystyle{ F \subseteq E \; }[/math] ребер графа G, такое, что для каждой пары полюсов [math]\displaystyle{ (s_i, t_i) \in R \; }[/math] существует путь между [math]\displaystyle{ s_i \; }[/math] и [math]\displaystyle{ t_i \; }[/math] в подграфе G[F], порожденном F. Пусть стоимость c(F) определяется как суммарная стоимость всех ребер в F, т.е. [math]\displaystyle{ c(F) = \sum_{e \in F} c(e) \; }[/math]. Задача заключается в нахождении допустимого решения F с минимальной стоимостью c(F). Легко заметить, что существует оптимальное решение, являющееся лесом.
Задачу построения леса Штейнера можно определить альтернативным образом при помощи не пар, а групп полюсов [math]\displaystyle{ R = \{ g_1, ..., g_k \} \; }[/math], где [math]\displaystyle{ g_i \subseteq V \; }[/math]. Задача заключается в вычислении подграфа с минимальной стоимостью, такого, что все полюса, принадлежащие к одной и той же группе, связаны друг с другом. Определение эквивалентно предыдущему.
Родственные задачи
Специальный случай задачи о лесе Штейнера представляет собой построение дерева Штейнера. Здесь все пары полюсов имеют общую корневую вершину [math]\displaystyle{ r \in V \; }[/math], т.е. [math]\displaystyle{ r \in \{ s_i, t_i \} \; }[/math] для всех пар полюсов [math]\displaystyle{ (s_i, t_i) \in R \; }[/math]. Иными словами, исходными данными задачи являются множество вершин полюсов [math]\displaystyle{ R \subseteq V \; }[/math] и корневая вершина [math]\displaystyle{ r \in V \; }[/math], а цель состоит в соединении полюсов из R с корневой вершиной r самым экономичным образом. Решением с минимальной стоимостью является дерево.
Задача построения обобщенной сети Штейнера, также известная как задача проектирования сети с повышенной живучестью (survivable network), представляет собой обобщение задачи построения леса Штейнера. Здесь функция требования соединения [math]\displaystyle{ r: V \times V \to \mathbb{N} \; }[/math] обозначает количество путей с непересекающимися ребрами, которые необходимо установить между каждой парой вершин. Иначе говоря, задача заключается в нахождении мульти-подмножества H ребер G с минимальной стоимостью (H может включать одно и то же ребро несколько раз), такого, что для каждой пары вершин [math]\displaystyle{ (x, y) \in V \; }[/math] имеется r(x, y) путей с непересекающимися ребрами из x в у в множестве G[H]. Задача заключается в нахождении множества H с минимальной стоимостью.
Очевидно, что в случае, когда [math]\displaystyle{ r(x, y) \in \{ 0, 1 \} \; }[/math] для всех [math]\displaystyle{ (x, y) \in V \times V \; }[/math], эта задача сводится к задаче построения леса Штейнера.
Основные результаты
Агравал, Клейн и Рави [1, 2] предложили алгоритм аппроксимации леса Штейнера с коэффициентом аппроксимации 2. Точнее говоря, авторы доказали следующую теорему.
Теорема 1. Существует алгоритм аппроксимации, который для каждого экземпляра I = (G, c, R) задачи построения леса Штейнера вычисляет допустимый лес F, такой, что [math]\displaystyle{ c(F) \le \Big( 2 - \frac{1}{k} \Big) \cdot OPT(I) \; }[/math], где k – количество пар полюсов в R, а OPT(I) – стоимость оптимального леса Штейнера для I.
Родственные работы
Задача построения дерева Штейнера является NP-полной [10] и APX-полной [4, 8]. Наилучшая известная нижняя граница достижимого коэффициента аппроксимации для решения этой задачи составляет 1,0074 [21]. Геманс и Уильямсон [11] обобщили результаты Агравала, Клейна и Рави для более широкого класса задач установления соединений, обозначив его как задачу построения леса с ограничениями. В случае построения леса Штейнера их алгоритм достигает того же коэффициента аппроксимации – (2 - 1/k). Алгоритмы Агравала, Клейна и Рави [2] и Геманса и Уильямсона основаны на классической формулировке задачи построения леса Штейнера с использованием неориентированных разрезов [3]. Известно, что разрыв целостности в этой релаксации составляет (2 - 1/k); таким образом, результаты в [2, 11] являются строгими. Джейн [15] представляет алгоритм 2-аппроксимации для задачи построения обобщенной сети Штейнера.
Прямо-двойственный алгоритм
Основная идея алгоритма Агравала, Клейна и Рави (AKR) изложена ниже. Описание отличается от приведенного в [2]; подробнее об этом – в той же работе.
Алгоритм основан на следующей формулировке задачи целочисленного программирования для построения леса Штейнера. Пусть I = (G, c, R) – экземпляр задачи построения леса Штейнера. Присвоим переменную-индикатор [math]\displaystyle{ x_e \in \{ 0, 1 \} \; }[/math] каждому ребру [math]\displaystyle{ e \in E \; }[/math]. Значение [math]\displaystyle{ x_e \; }[/math] равно 1, если e является частью леса F, и 0 в противном случае. Подмножество [math]\displaystyle{ S \subseteq V \; }[/math] вершин называется разрезом Штейнера, если существует по меньшей мере одна пара полюсов [math]\displaystyle{ (s_i, t_i) \in R \; }[/math], такая, что [math]\displaystyle{ | \{ s_i, t_i \} \cap S | = 1 \; }[/math]; говорят, что S разделяет пару полюсов [math]\displaystyle{ (s_i, t_i) \; }[/math]. Пусть S – множество всех разрезов Штейнера. Для подмножества [math]\displaystyle{ S \subseteq V \; }[/math] определим [math]\displaystyle{ \delta (S) \; }[/math] как множество всех ребер в E, имеющих ровно одну конечную точку в S. Пусть дан разрез Штейнера [math]\displaystyle{ S \in S \; }[/math]; любое допустимое решение F для экземпляра I должно содержать по меньшей мере одно ребро, пересекающее разрез S, т.е. [math]\displaystyle{ \sum_{e \in \delta (S)} x_e \ge 1 \; }[/math]. Это приводит к следующей формулировке задачи с неориентированными разрезами:
(IP) минимизировать [math]\displaystyle{ \sum_{e \in E} c(e) x_e \; }[/math]
(1) относительно [math]\displaystyle{ \sum_{e \in \delta (S)} x_e \ge 1 \; \forall S \in S }[/math]
(2) [math]\displaystyle{ x_e \in \{ 0, 1 \} \; \forall e \in E }[/math]
Двойственная задача для релаксации линейного программирования (IP) включает переменную [math]\displaystyle{ y_S \; }[/math] для каждого разреза Штейнера [math]\displaystyle{ S \in S \; }[/math]. Существует ограничение: для каждого ребра [math]\displaystyle{ e \in E \; }[/math] полная двойственная задача, присвоенная множествам [math]\displaystyle{ S \in S \; }[/math], содержащим только одну конечную точку e, имеет стоимость не более c(e):
(D) максимизировать [math]\displaystyle{ \sum_{S \in S} y_S }[/math]
(3) относительно [math]\displaystyle{ \sum_{S \in S: \; e \in \delta (S)} y_S \le c(e) \; \forall e \in E }[/math]
(4) [math]\displaystyle{ y_S \ge 0 \; \forall S \in S }[/math]
Алгоритм AKR основан на прямо-двойственной схеме (см., например, [22]). Он строит и допустимое прямое решение для (IP), и допустимое двойственное решение для (D). Алгоритм начинает работу с недопустимого прямого решения, снижая степень его недопустимости по мере продвижения. В то же время он создает допустимый набор двойственных подмножеств с большой общей суммой, вводя двойственные переменные для разрезов Штейнера.
Можно рассмотреть выполнение алгоритма AKR как процесса, зависящего от времени. Пусть [math]\displaystyle{ x^{ \tau} \; }[/math] и [math]\displaystyle{ y^{ \tau} \; }[/math] обозначают вектор инцидентности прямой задачи и допустимое решение двойственной задачи в момент времени [math]\displaystyle{ \tau \; }[/math], соответственно. Вначале положим [math]\displaystyle{ x^0_e = 0 \; }[/math] для всех ребер [math]\displaystyle{ e \in E \; }[/math] и [math]\displaystyle{ y^0_S = 0 \; }[/math] для всех подмножеств [math]\displaystyle{ S \in S \; }[/math]. Пусть [math]\displaystyle{ F^{ \tau} \; }[/math] обозначает лес, соответствующий множеству ребер с [math]\displaystyle{ x^{ \tau} = 1 \; }[/math]. Дерево T в лесу [math]\displaystyle{ F^{ \tau} \; }[/math] называется активным в момент времени [math]\displaystyle{ \tau \; }[/math], если оно содержит полюс, отделенный от своей пары; в противном случае оно называется неактивным. Интуитивно понятно, что алгоритм AKR растит активные деревья в [math]\displaystyle{ F^{ \tau} \; }[/math]. В то же время он увеличивает двойственные значения разрезов Штейнера, соответствующие активным деревьям. Если два активных дерева сталкиваются, они сливаются вместе. Процесс заканчивается, когда все деревья оказываются неактивными и, следовательно, не остается несвязанных пар полюсов. Взаимодействие между прямым (ростом деревьев) и обратным (увеличением двойственных значений) процессами представляет собой довольно тонкое явление.
Ребро [math]\displaystyle{ e \in E \; }[/math] является плотным, если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все составляющего его ребра являются плотными. Пусть [math]\displaystyle{ H^{ \tau} \; }[/math] – подграф G, порожденный плотными ребрами для двойственного значения [math]\displaystyle{ y^{ \tau} \; }[/math]. Связные компоненты [math]\displaystyle{ H^{ \tau} \; }[/math] порождают разбиение [math]\displaystyle{ C^{ \tau} \; }[/math] на множестве вершин V. Пусть [math]\displaystyle{ S^{ \tau} \; }[/math] – множество всех разрезов Штейнера, содержащихся в [math]\displaystyle{ C^{ \tau} \; }[/math], т.е. [math]\displaystyle{ S^{ \tau} = C^{ \tau} \cap S \; }[/math]. Алгоритм AKR равномерно увеличивает двойственные значения [math]\displaystyle{ y_S \; }[/math] для всех множеств [math]\displaystyle{ S \in S^{ \tau} \; }[/math] во все моменты времени [math]\displaystyle{ \tau \ge \gt 0 \; }[/math]. Заметим, что [math]\displaystyle{ y^{ \tau} \; }[/math] является допустимым для двойственной задачи. Алгоритм поддерживает инвариант: [math]\displaystyle{ F^{ \tau} \; }[/math] в любой момент времени является подграфом [math]\displaystyle{ H^{ \tau} \; }[/math]. Рассмотрим событие, при котором путь P между двумя деревьями [math]\displaystyle{ T_1 \; }[/math] и [math]\displaystyle{ T_2 \; }[/math] в [math]\displaystyle{ F^{ \tau} \; }[/math] становится плотным. После этого недостающие ребра P добавляются к [math]\displaystyle{ F^{ \tau} \; }[/math] и процесс продолжается. В конечном итоге все деревья [math]\displaystyle{ F^{ \tau} \; }[/math] становятся неактивными, в результате чего процесс завершается.
Применение
Вычисление (приближенных) решений задачи построения леса Штейнера имеет немало теоретических и практических вариантов применения; отметим только самые недавние разработки. Алгоритмы проектирования сетей сложной конструкции нередко полагаются на качественные алгоритмы аппроксимации для леса Штейнера. Например, недавно опубликованные алгоритмы аппроксимации [6, 9, 12] для задачи построения многопродуктовой сети покупки или аренды (multi-commodity rent-or-buy problem, MRoB) основаны на структуре случайной выборки Гупты и др. [12,13]. Эта структура использует алгоритм аппроксимации леса Штейнера, удовлетворяющий определенному свойству строгости, заданному в виде дополнительной подпрограммы. Флейшер и др. [9] показали, что алгоритм AKR удовлетворяет этому свойству строгости, благодаря чему был разработан лучший на данный момент алгоритм 5-аппроксимации для MRoB. Свойство строгости также играет важнейшую роль в структуре выборки с усилением, предложенной Гуптой и др. [14] для задач двухступенчатой стохастической оптимизации с регрессом.
Онлайн-версии алгоритмов построения дерева и леса Штейнера изучали Авербух и др. [5], а также Берман и Коулстон [7]. В области алгоритмической теории игр разработка механизмов распределения затрат в рамках групповой стратегии для задач проектирования сетей – таких как задача построения дерева Штейнера – недавно удостоилась широкого внимания исследователей; см., например, [16, 17, 19, 20]. Адаптация алгоритма AKR позволила получить подобный механизм распределения затрат для задачи построения леса Штейнера [18].
См. также
Литература
Обратитесь к статьям [2, 11] за более детальным описанием прямо-двойственных алгоритмов аппроксимации для задач проектирования сетей общего вида.
1. Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. In: Proc. of the 23rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, pp. 134-144(1991)
2. Agrawal, A., Klein, P., Ravi, R.: When trees collide: An approximation algorithm for the generalized Steiner problem in networks. SIAM J. Comput. 24(3),445-456 (1995)
3. Aneja, Y.P.: An integer linear programming approach to the Steiner problem in graphs. Networks 10(2), 167-178 (1980)
4. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501-555 (1998)
5. Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized Steiner problem. In: Proc. of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, 2005, pp. 68-74 (1996)
6. Becchetti, L, Konemann, J., Leonardi, S., Pal, M.: Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, pp. 375-384 (2005)
7. Berman, P., Coulston, C.: On-line algorithms for Steiner tree problems. In: Proc. of the 29th Annual ACM Symposium on Theory of Computing, pp. 344-353. Association for Computing Machinery, New York(1997)
8. Bern, M., Plassmann, P.:The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32(4), 171-176 (1989)
9. Fleischer, L., Konemann, J., Leonardi, S., Schafer, G.: Simple cost-sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree. In: Proc. of the 38th Annual ACM Symposium on Theory of Computing, pp. 663-670. Association for Computing Machinery, New York (2006)
10. Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco (1979)
11. Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2),296-317(1995)
12. Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: a simple approximation algorithm for the multicommodity rent-or-buy problem. In: Proc. of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 606-617., IEEE Computer Society, Washington (2003)
13. Gupta, A., Kumar, A., Pal, M., Roughgarden, T.: Approximation via cost-sharing: simpler and better approximation algorithms for network design. J. ACM 54(3), Article 11 (2007)
14. Gupta, A., Pal, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proc. of the 36th Annual ACM Symposium on Theory of Computing, pp. 417-426. Association for Computing Machinery, New York (2004)
15. Jain, K.: A factor 2 approximation for the generalized Steiner network problem. Combinatorica 21 (1), 39-60 (2001)
16. Jain, K., Vazirani, V.V.: Applications of approximation algorithms to cooperative games. In: Proc. of the 33rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York, pp. 364-372 (2001)
17. Kent, K., Skorin-Kapov, D.: Population monotonic cost allocation on mst's. In: Proc. of the 6th International Conference on Operational Research, Croatian Operational Research Society, Zagreb, pp. 43-48 (1996)
18. Konemann, J., Leonardi, S., Schafer, G.: A group-strategyproof mechanism for Steiner forests. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 612-619. Society for Industrial and Applied Mathematics, Philadelphia (2005)
19. Megiddo, N.: Cost allocation for Steiner trees. Networks 8(1), 1-6(1978)
20. Moulin, H., Shenker, S.: Strategyproof sharing of submodular costs: budget balance versus efficiency. Econ. Theor. 18(3), 511-533(2001)
21. Thimm, M.: On the approximability of the Steiner tree problem. Theor. Comput. Sci. 295(1-3), 387-402 (2003)
22. Vazirani, V.V.: Approximation algorithms. Springer, Berlin (2001)