Минимальные 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]. В более общем виде стоимость можно определить с использованием других норм – таких как lp-нормы для любого p > 1, т.е. [math]\displaystyle{ \delta(x, y) = ( \sum_{i=1}^p (x_i - y_i)^p)^{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 \; }[/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 точек в R и функции требования связности r:SxS^-N найти геометрическую сеть минимальной стоимости, охватывающую точки из S, такую, что для любой пары вершин p, q 2 S подсеть имеет грл внутренне вершинно-непересекающихся (или реберно-непересекащихся, соответственно) путей между p и q.

Во многих приложениях этой задачи, нередко считающихся наиболее интересными [9, 13], функция требования связности определяется при помощи функции от одного аргумента, присваивающей каждой вершине p ее тип связности rv 2 N. Тогда для любой пары вершин p, q 2 S требование связности Грл задается просто в виде minfrp; rqg [12, 13, 17, 18]. В число таких приложений входит задача о вычислении дерева Штейнера, (см., например, [ ]), в которой rp 2 f0; 1g для любой вершины p2S.

Схема аппроксимации с полиномиальным временем выполнения (PTAS) представляет собой семейство алгоритмов fA" g, такое, что для каждого фиксированного " > 0 алгоритм A" исполняется за время, полиномиальное относительно размера входного графа, и обеспечивает (1 + ")-аппроксимацию.

Родственные работы

Исчерпывающий обзор результатов решения задач о нахождении k-вершинно-связных или k-реберно-связных остовных подграфов с минимальной стоимостью, задач о неоднородной связности, задач о пополнении связности и геометрических задач приведен в работах [1, 3, 11, 15].

Несмотря на высокую практическую значимость задач о многосвязности в геометрических сетях и большое количество опубликованных практических эвристических результатов (см., например, [12, 13, 17, 18]), до недавнего времени совсем небольшое число теоретических исследований было посвящено разработке эффективных алгоритмов аппроксимации этих задач. Эта ситуация резко контрастирует с обширным списком успешных теоретических исследований соответствующих задач на общеметрических пространствах и для взвешенных графов общего вида. Таким образом, до 1998 года даже для самой простой и наиболее фундаментальной задачи о многосвязности, а именно – задачи о нахождении 2-вершинно-связной сети минимальной стоимости, охватывающей заданный набор точек на евклидовой плоскости, не удавалось получить аппроксимации с лучшим коэффициентом, чем | (коэффициент | представляет собой наилучший известный коэффициент аппроксимации с полиномиальным временем выполнения для сетей общего вида, веса в которых удовлетворяют неравенству треугольника [8]. Другие результаты можно найти в [4, 15]).

Основные результаты

Первым результатом является расширение хорошо известного понятия о NP-полноте задачи нахождения 2-связной сети минимальной стоимости в графах общего вида (см., например, [ ]) на геометрические сети.

Теорема 1. Задача нахождения 2-вершинно/реберно-связной геометрической сети минимальной стоимости, охватывающей набор из n точек на плоскости, является NPT-полной.

Следующий результат показывает, что если рассматривать задачи о многосвязности с нахождением объектов минимальной стоимости для достаточно большой размерности, эти задачи становятся APX-полными.

Теорема 2 ([6]). Существует константа £ > 0, такая, что задача аппроксимации 2-связной геометрической сети минимальной стоимости, охватывающей набор из n точек в Rdlog2ne, с коэффициентом 1 + % является NPT-полной.

Этот результат также можно расширить на любую lp-норму.

Теорема 3 ([6]). Для любого целого числа d > log n и любого фиксированного p > 1 существует константа £ > 0, такая, что задача аппроксимации 2-связной сети минимальной стоимости, охватывающей набор из n точек в метрике lp в пространстве Rd, с коэффициентом 1 + % является NP-полной.

Поскольку задачи о многосвязности с нахождением объектов минимальной стоимости довольно сложны, исследователи обращаются к алгоритмам аппроксимации. Объединяя некоторые идеи, сформулированные Аророй [ ] (см. также [ ]) для алгоритмов аппроксимации задачи коммивояжера с полиномиальным временем выполнения, с несколькими новыми идеями, разработанными специально для решения задач о многосвязности в геометрических сетях, Шумай и Лингас получили следующие результаты.

Теорема 4 ([5, 6]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ (log n)(kd/")O(d) ■ 22(kd/")O(d) с вероятностью не менее 0,99 находит k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную.

Кроме того, этот алгоритм может быть дерандомизирован за полиномиальное время с тем, чтобы возвращать k-вершинно-связную (или k-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную.

Заметим, что в случае, если все значения d, k и " являются константными, время выполнения составляет n • logO(1) n.

Результат теоремы 4 позволяет получить схему аппроксимации с полиномиальным временем исполнения (PTAS) для малых значений k и d.

Теорема 5 (PTAS для вершинной или реберной связности [6, 5]). Пусть d > 2 – любое константное целое число. Существует определенная положительная константа c < 1, такая, что для всех k < (loglogn)c задачи построения k-вершинно-связной или k-реберно-связной остовной сети минимальной стоимости для множества точек в пространстве Rd допускают использование PTAS.

В следующей теореме рассматриваются мультисети, в которых допустимые решения могут использовать параллельные ребра.

Теорема 6 ([5]). Пусть k и d – любые целые числа, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ (log n)(kd/")O(d) ■ 0(kd/")O(d) с вероятностью не менее 0,99 находит k-реберно-связную остовную мультисеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Сочетая формулировку данной теоремы с тем фактом, что параллельные ребра можно удалить в случае k = 2, получаем следующий результат для задачи 2-связности в сетях.

Теорема 7 (Схемы аппроксимации для 2-связных графов, [5]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Для константного значения d время выполнения рандомизированных алгоритмов составляет nlog n • (1/")O(1) + 2(1/")O(1).

Теорема 8 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) + n-2{dls)°{i2) + n-22i с вероятностью не менее 0,99 находит 2-вершинно-связную (или 2-реберно-связную) остовную сеть Штейнера для S, стоимость которой не более чем в (1 + ") раз превышает оптимальную. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Теорема 9 ([7]). Пусть d – любое целое число, d > 2, а " – любое положительное вещественное число. Пусть S – множество из n точек в пространстве Rd. Существует рандомизированный алгоритм, который за время n ■ log n • (d/")O(d) + n-2ldle)°(d ) + n-22d с вероятностью не менее 0,99 решает задачу построения геометрической сети с повышенной живучестью с rv 2 f0; 1; 2g для любого v 2 V. Этот алгоритм может быть дерандомизирован за полиномиальное время.

Применение

Multi-connectivity problems are central in algorithmic graph theory and have numerous applications in computer science and operation research, see, e.g., [1,13, 11,18]. They also play very important role in the design of networks that arise in practical situations, see, e.g., [1,13]. Typical application areas include telecommunication, computer and road networks. Low degree connectivity problems for geometrical networks in the plane can often closely approximate such practical connectivity problems (see, e.g., the discussion in [13,17,18]). The survivable network design problem in geometric networks also arises in many applications, e. g., in telecommunication, communication network design, VLSI design, etc. [12,13,17,18].

Open Problems The results discussed above lead to efficient algorithms only for small connectivity requirements k; the running-time is polynomial only for the value of k up to (log log n) for certain positive constant c < 1. It is an interesting open problem if one can obtain polynomial-time approximation schemes algorithms also for large values of k.

It is also an interesting open problem if the multi-connectivity problems in geometric networks can have practically fast approximation schemes.

См. также

► Euclidean Traveling Salesperson Problem ► Minimum Geometric Spanning Trees

Литература

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)