Минимальные k-связные геометрические сети
Ключевые слова и синонимы
Геометрические графы; евклидовы графы
Постановка задачи
Рассматривается следующая классическая задача оптимизации: для заданной неориентированной взвешенной геометрической сети найти подсеть минимальной стоимости, удовлетворяющую заданным априори требованиям многосвязности.
Нотация
Пусть G = (V, E) – геометрическая сеть, множество вершин V которой соответствует множеству из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] для определенного целого числа [math]\displaystyle{ d \ge 2 \; }[/math], а множество ребер E – множеству прямолинейных сегментов, соединяющих пары точек из V. Сеть G называется полной, если E соединяет все пары точек из V.
Стоимость [math]\displaystyle{ \delta(x, y) \; }[/math] дуги, соединяющей пару точек [math]\displaystyle{ x, y \in \mathbb{R}^d \; }[/math], равна евклидовому расстоянию между точками x и y. Иначе говоря, [math]\displaystyle{ \delta(x, y) = \sqrt{ \sum^d_{i=1} (x_i - y_i)^2} }[/math], где [math]\displaystyle{ x = (x_1, ..., x_d) \; }[/math] и [math]\displaystyle{ y = (y_1, ..., y_d) \; }[/math]. В более общем виде стоимость можно определить с использованием других норм – таких как [math]\displaystyle{ \ell_p }[/math]-нормы для любого p > 1, т.е. [math]\displaystyle{ \delta(x, y) = \Big( \sum_{i=1}^p (x_i - y_i)^p \Big)^{1/p} \; }[/math]. Стоимость сети равна сумме стоимостей всех ребер сети: [math]\displaystyle{ cost(G) = \sum_{x, y \in E} \delta(x, y) \; }[/math].
Сеть G = (V, E) служит остовом множества точек S (охватывает множество точек S), если V = S. Сеть G является k-вершинно-связной, если для любого множества [math]\displaystyle{ U \subseteq V \; }[/math], состоящего из менее чем k вершин, сеть [math]\displaystyle{ (V \backslash U, E \cap ((V \backslash U) \times (V \backslash U)) }[/math] является связной. Подобным же образом G является k-реберно-связной, если для любого множества [math]\displaystyle{ \mathcal{E} \subseteq E \; }[/math] с количеством ребер менее k сеть [math]\displaystyle{ (V, E \backslash \mathcal{E}) \; }[/math] является связной.
(Евклидова) задача нахождения k-вершинно-связной остовной сети минимальной стоимости
Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-вершинно-связную евклидову сеть минимальной стоимости, охватывающую точки S.
(Евклидова) задача нахождения k-реберно-связной остовной сети минимальной стоимости
Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-реберно-связную евклидову сеть минимальной стоимости, охватывающую точки S.
Рассматривается также вариант, допускающий наличие параллельных ребер:
(Евклидова) задача нахождения k-реберно-связной остовной мультисети минимальной стоимости
Для заданного множества S из n точек в евклидовом пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] найти k-реберно-связную евклидову мультисеть минимальной стоимости, охватывающую точки S (под мультисетью понимается сеть, допускающая наличие параллельных ребер.
Понятие k-связности с минимальной стоимостью естественным образом расширяется на k-связность евклидовой сети Штейнера, если разрешить использование дополнительных вершин, называемых точками Штейнера. Для заданного набора точек S в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] геометрическая сеть G представляет собой k-вершинно-связную (или k-реберно-связную) сеть Штейнера для S, если множество вершин G является надмножеством S и для каждой пары точек из S существует k внутренне вершинно-непересекающихся (реберно-непересекащихся, соответственно) путей, соединяющих их в G.
(Евклидова) задача нахождения k-вершинно/реберно-связной сети Штейнера минимальной стоимости
Найти сеть минимальной стоимости на надмножестве S, являющуюся k-вершинно/реберно-связной сетью Штейнера для S.
Заметим, что при k = 1 эта задача представляет собой просто задачу построения минимального дерева Штейнера, которой посвящено множество работ (см., например, [14]).
В более общей формулировке задач о многосвязности в графах следует учитывать неоднородные ограничения связности.
Задача построения сети с повышенной живучестью
Для заданного набора S точек в [math]\displaystyle{ \mathbb{R}^d \; }[/math] и функции требования связности [math]\displaystyle{ r: S \times S \to \mathbb{N} \; }[/math] найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин [math]\displaystyle{ p, q \in S \; }[/math] подсеть имеет [math]\displaystyle{ r_{p, q} \; }[/math] внутренне вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q.
Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности [math]\displaystyle{ r_v \in \mathbb{N} \; }[/math]. Тогда для любой пары вершин [math]\displaystyle{ p, q \in S \; }[/math] требование связности [math]\displaystyle{ r_{p, q} \; }[/math] задается просто в виде [math]\displaystyle{ min \{ r_p, r_q \} \; }[/math] [12, 13, 17, 18]. В число таких приложений входит задача о вычислении дерева Штейнера, (см., например, [2]), в которой [math]\displaystyle{ r_p \in \{ 0, 1 \} \; }[/math] для любой вершины [math]\displaystyle{ p \in S \; }[/math].
Аппроксимационная схема с полиномиальным временем выполнения (PTAS) представляет собой семейство алгоритмов [math]\displaystyle{ \{ \mathcal{A}_\varepsilon \} \; }[/math], такое, что для каждого фиксированного [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] алгоритм [math]\displaystyle{ \mathcal{A}_\varepsilon \; }[/math] исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию.
Родственные работы
Исчерпывающий обзор результатов решения задач о нахождении k-вершинно-связных или k-реберно-связных остовных подграфов с минимальной стоимостью, задач о неоднородной связности, задач о пополнении связности и геометрических задач приведен в работах [1, 3, 11, 15].
Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем небольшое число теоретических исследований было посвящено разработке эффективных аппроксимационных алгоритмов этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач на общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем [math]\displaystyle{ \frac{3}{2} }[/math] (где [math]\displaystyle{ \frac{3}{2} }[/math] – это наилучший известный коэффициент аппроксимации с полиномиальным временем выполнения для сетей общего вида, веса в которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).
Основные результаты
Первым результатом является расширение хорошо известного понятия о NP-полноте задачи нахождения 2-связной сети минимальной стоимости в графах общего вида (см., например, [10]) на геометрические сети.
Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NP-полной.
Следующий результат показывает, что если рассматривать задачи о многосвязных объектах минимальной стоимости при достаточно большой размерности, эти задачи становятся APX-полными.
Теорема 2 ([6]). Существует константа [math]\displaystyle{ \xi \gt 0 \; }[/math], такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в [math]\displaystyle{ \mathbb{R}^{\lceil log_2 \; n \rceil} }[/math], с коэффициентом [math]\displaystyle{ 1 + \xi \; }[/math] является NP-полной.
Этот результат также можно расширить на любую [math]\displaystyle{ \ell_p }[/math]--норму.
Теорема 3 ([6]). Для любого целого числа [math]\displaystyle{ d \ge log \; n }[/math] и любого фиксированного [math]\displaystyle{ p \ge 1 \; }[/math] существует константа [math]\displaystyle{ \xi \gt 0 \; }[/math], такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике [math]\displaystyle{ \ell_p }[/math]- в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math], с коэффициентом [math]\displaystyle{ 1 + \xi \; }[/math] является NP-полной.
Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к аппроксимационным алгоритмам. Объединяя некоторые идеи, сформулированные Аророй [2] (см. также [6]) для аппроксимационных алгоритмов задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты.
Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, [math]\displaystyle{ k, d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot (log \; n)^{(kd / \varepsilon)^{O(d)}} \cdot 2^{2^{(kd / \varepsilon)^{O(d)}}} }[/math] с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную.
Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную.
Заметим, что в случае, если все значения d, k и [math]\displaystyle{ \varepsilon \; }[/math] являются константными, время выполнения составляет [math]\displaystyle{ n \cdot log^{O(1)} \; n }[/math].
Результат теоремы 4 позволяет получить аппроксимационную схему с полиномиальным временем выполнения (PTAS) для малых значений k и d.
Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть [math]\displaystyle{ d \ge 2 \; }[/math] – любое константное целое число. Существует определенная положительная константа [math]\displaystyle{ c \lt 1 \; }[/math], такая, что для всех [math]\displaystyle{ k \le (log \; log \; n)^c }[/math] задача построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math] допускает использование PTAS.
В следующей теореме рассматриваются мультисети, в которых допустимые решения могут использовать параллельные ребра.
Теорема 6 ([5]). Пусть k и d – любые целые числа, [math]\displaystyle{ k, d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{2^{(k^{O(1)} \cdot d / \varepsilon)^{O(d^2)})}} }[/math] с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.
Сочетая формулировку данной теоремы с тем фактом, что параллельные ребра можно удалить в случае k = 2, получаем следующий результат для задачи 2-связности в сетях.
Теорема 7 (Аппроксимационные схемы для 2-связных графов, [5]). Пусть d – любое целое число, [math]\displaystyle{ d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} }[/math] с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.
Для константного значения d время выполнения рандомизированных алгоритмов составляет [math]\displaystyle{ n \; log \; n \cdot (1 / \varepsilon)^{O(1)} + 2^{(1 / \varepsilon)^{O(1)}} }[/math].
Теорема 8 ([7]). Пусть d – любое целое число, [math]\displaystyle{ d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}} }[/math] с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.
Теорема 9 ([7]). Пусть d – любое целое число, [math]\displaystyle{ d \ge 2 \; }[/math], а [math]\displaystyle{ \varepsilon \; }[/math] – любое положительное вещественное число. Пусть S – множество из n точек в пространстве [math]\displaystyle{ \mathbb{R}^d \; }[/math]. Существует рандомизированный алгоритм, который за время [math]\displaystyle{ n \cdot log \; n \cdot (d / \varepsilon)^{O(d)} + n \cdot 2^{(d / \varepsilon)^{O(d^2)}} + n \cdot 2^{2^{d^{d^{O(1)}}}} }[/math] с вероятностью не менее 0,99 находит [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимацию геометрической сети с повышенной живучестью с [math]\displaystyle{ r_v \in \{ 0, 1, 2 \} \; }[/math] для любого [math]\displaystyle{ v \in V \; }[/math]. Этот алгоритм может быть дерандомизирован за полиномиальное время.
Применение
Задачи о многосвязности занимают центральное место в алгоритмической теории графов и широко применяются в сферах вычислительных наук и исследования операций – см., например, [1, 13, 11, 18]. Они также играют исключительно важную роль в решении задач о построении сетей, возникающих во многих практических ситуациях [1, 13]. Среди типичных областей применения можно упомянуть телекоммуникации, компьютерные и улично-дорожные сети. Задачи о связности низкой степени для геометрических сетей на плоскости нередко могут достаточно точно аппроксимировать подобные практические задачи (см., например, обсуждение в [13, 17, 18]). Задача построения сети с повышенной живучестью в геометрических сетях также возникает во множестве практических ситуаций – в частности, в телекоммуникациях, при проектировании сетей телекоммуникаций, проектировании СБИС и т.п. [12, 13, 17, 18].
Открытые вопросы
Вышеприведенные результаты позволяют создавать эффективные алгоритмы только для малых значений требования связности k; время выполнения является полиномиальным только для значения k, не превышающего [math]\displaystyle{ (log \; log \; n)^c }[/math] для определенной положительной константы c < 1. Любопытно было бы узнать, можно ли получить алгоритм аппроксимационной схемы с полиномиальным временем выполнения для больших значений k.
Еще один интересный открытый вопрос заключается в том, можно ли разработать достаточно быструю для практического применения аппроксимационную схему решения задачи о многосвязности в геометрических сетях.
См. также
Литература
1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B., Reddy, M.R.: Applications of network optimization. In: Handbooks in Operations Research and Management Science, vol. 7, Network Models, chapter 1,pp. 1-83. North-Holland, Amsterdam (1995)
2. Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782 (1998)
3. Berger, A., Czumaj, A., Grigni, M., Zhao, H.: Approximation schemes for minimum 2-connected spanning subgraphs in weighted planar graphs. Proc. 13th Annual European Symposium on Algorithms, pp. 472^83. (2005)
4. Cheriyan, J., Vetta, A.: Approximation algorithms for network design with metric costs. Proc. 37th Annual ACM Symposium on Theory of Computing, Baltimore, 22-24 May 2005, pp. 167-175.(2005)
5. Czumaj, A., Lingas, A.: Fast approximation schemes for Euclidean multi-connectivity problems. Proc. 27th Annual International Colloquium on Automata, Languages and Programming, Geneva, 9-15 July 2000, pp. 856-868
6. Czumaj, A., Lingas, A.: On approximability of the minimum-cost k-connected spanning subgraph problem. Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, 17-19 January 1999, pp. 281-290
7. Czumaj, A., Lingas, A., Zhao, H.: Polynomial-time approximation schemes for the Euclidean survivable network design problem. Proc. 29th Annual International Colloquium on Au tomata, Languages and Programming, Malaga, 8-13 July 2002, pp. 973-984
8. Frederickson, G.N., JaJa, J.: On the relationship between the biconnectivity augmentation and Traveling Salesman Problem. Theor. Comput. Sci. 19(2), 189-201 (1982)
9. Gabow, H.N., Goemans, M.X., Williamson, D.P.: An efficient approximation algorithm for the survivable network design problem. Math. Program. Ser. B 82(1-2), 13-40 (1998)
10. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York, NY (1979)
11. Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, Chapter 4, pp. 144-191. PWS Publishing Company, Boston (1996)
12. Grotschel, M., Monma, C.L., Stoer, M.: Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Oper. Res. 40(2), 309-330(1992)
13. Grotschel, M., Monma, C.L., Stoer, M.: Design of survivable net works. In: Handbooks in Operations Research and Manage ment Science, vol. 7, Network Models, chapter 10, pp. 617-672. North-Holland, Amsterdam (1995)
14. Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland, Amsterdam (1992)
15. Khuller, S.: Approximation algorithms for finding highly connected subgraphs. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-Hard Problems, Chapter 6, pp. 236-265. PWS Publishing Company, Boston (1996)
16. Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298-1309 (1999)
17. Monma, C.L., Shallcross, D.F.: Methods for designing communications networks with certain two-connected survivability constraints. Operat. Res. 37(4), 531-541 (1989)
18. Stoer, M.: Design of Survivable Networks. Springer, Berlin (1992)