Минимальные 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, если 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]).

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

Задача конструирования сети с повышенной живучестью For a given set S of points in R and a connectivity requirement function r:SxS^-N, find a minimum-cost geometric network spanning points in S such that for any pair of vertices p;q 2 S the sub-network has грл internally vertex-disjoint (or edge-disjoint, respectively) paths between p and q. For a given set S of points in R and a connectivity requirement function r:SxS^-N, find a minimum-cost geometric network spanning points in S such that for any pair of vertices p;q 2 S the sub-network has грл internally vertex-disjoint (or edge-disjoint, respectively) paths between p and q.

In many applications of this problem, often regarded as the most interesting ones [9,13], the connectivity requirement function is specified with the help of a one-argument function which assigns to each vertex p its connectivity type rv 2 N. Then, for any pair of vertices p; q 2 S, the connectivity requirement Грл is simply given as minfrp; rqg [12,13,17,18]. This includes the Steiner tree problem (see, e. g., [ ]), in which rp 2 f0; 1g for any vertex p2S.

A polynomial-time approximation scheme (PTAS) is a family of algorithms fA"g such that, for each fixed " > 0, A" runs in time polynomial in the size of the input and produces a (1 + ")-approximation.

Related Work For a very extensive presentation of results concerning problems of finding minimum-cost k-vertex- and k-edge-connected spanning subgraphs, non-uniform connectivity, connectivity augmentation problems, and geometric problems, see [1,3,11,15].

Despite the practical relevance of the multi-connectivity problems for geometrical networks and the vast amount of practical heuristic results reported (see, e.g., [12,13,17,18]), very little theoretical research had been done towards developing efficient approximation algorithms for these problems until a few years ago. This contrasts with the very rich and successful theoretical investigations of the corresponding problems in general metric spaces and for general weighted graphs. And so, until 1998, even for the simplest and most fundamental multi-connectivity problem, that of finding a minimum-cost 2-vertex connected network spanning a given set of points in the Euclidean plane, obtaining approximations achieving better than a | ratio had been elusive (the ratio

| is the best polynomial-time approximation ratio known for general networks whose weights satisfy the triangle inequality [8]; for other results, see e. g., [4,15]).

Key Results The first result is an extension of the well-known NP-hardness result of minimum-cost 2-connectivity in general graphs (see, e. g., [ ]) to geometric networks.

Theorem 1 The problem of finding a minimum-cost 2-vertex/edge connected geometric network spanning a set of n points in the plane is NP T-hard.

Next result shows that if one considers the minimum-cost multi-connectivity problems in an enough high dimension, the problems become APX-hard.

Theorem 2 ([6]) There exists a constant £ > 0 such that it is NP-hard to approximate within 1 + % the minimum-cost 2-connected geometric network spanning a set of n points in Rdlog2ne.

This result extends also to any lp norm.

Theorem 3 ([6]) For and integer d > log n and for any fixed p > 1 there exists a constant f > 0 such that it is NP-hard to approximate within 1 + f the minimum-cost 2-connected network spanning a set of n points in the lp metric in Rd.

Since the minimum-cost multi-connectivity problems are hard, the research turned into the study of approximation algorithms. By combining some of the ideas developed for the polynomial-time approximation algorithms for TSP due to Arora [ ] (see also [ ]) together with several new ideas developed specifically for the multi-connectivity problems in geometric networks, Czumaj and Lingas obtained the following results.

Theorem 4 ([5,6]) Let k and d be any integers, k; d > 2, and let " be any positive real. Let S be a set of n points in Rd. There is a randomized algorithm that in time n ■ (log n)(kd/")O(d) ■ 22(kd/")O(d) with probability at least 0.99 finds a k-vertex-connected (or k-edge-connected) spanning network for S whose cost is at most (1 + ")-time optimal.

Furthermore, this algorithm can be derandomized in polynomial-time to return a k-vertex-connected (or k-edge-connected) spanning network for S whose cost is at most (1 + ") times the optimum.

Observe that when all d, k, and " are constant, then the running-times are n • logO(1) n. The results in Theorem 4 give a PTAS for small values of k and d.

Theorem 5 (PTAS for vertex/edge-connectivity [6,5]) Letd > 2 be any constant integer. There is a certain positive constant c < 1 such that for all k such that k < (loglogn)c, the problems of finding a minimum-cost k-vertex-connected spanning network and a k-edge-connected spanning network for a set of points in Rd admit PTAS.

The next theorem deals with multi-networks where feasible solutions are allowed to use parallel edges.

Theorem 6 ([5]) Let k and d be any integers, k; d > 2, and let " be any positive real. Let S be a set of n points in Rd. There is a randomized algorithm that in time n ■ log n • (d/")O(d) + n ■ 2^k0(l)idls)0(d )}, with probability at least 0.99 finds a k-edge-connected spanning multi-network for S whose cost is at most (1 + ") times the optimum. The algorithm can be derandomized in polynomial-time.

Combining this theorem with the fact that parallel edges can be eliminated in case k = 2, one obtains the following result for 2-connectivity in networks.

Theorem 7 (Approximation schemes for 2-connected graphs, [5]) Let d be any integer, d > 2, and let " be any positive real. Let Sbe a set ofn points in Rd. There is a randomized algorithm that in time n ■ log n • (d/")O(d) + n ■ 2(d/")O(d ^ with probability at least 0.99 finds a 2-vertex-connected (or 2-edge-connected) spanning network for S whose cost is at most (1 + ") times the optimum. This algorithm can be derandomized in polynomial-time.

For constant d the running time of the randomized algorithms is nlog n • (1/")O(1) + 2(1/")O(1).

Theorem 8 ([7]) Let d be any integer, d > 2, and let " be any positive real. Let S be a set of n points in Rd. There is a randomized algorithm that in time n ■ log n • (d/")O(d) + n-2{dls)°{i2) + n-22i , with probability at least 0.99 finds a Steiner 2-vertex-connected (or 2-edge-connected) spanning network for S whose cost is at most (1 + ") times the optimum. This algorithm can be derandomized in polynomial-time.

Theorem 9 ([7]) Let d be any integer, d > 2, and let " be any positive real. Let S be a set of n points in Rd. There is a randomized algorithm that in time n ■ log n • (d/")O(d) + n-2ldle)°(d ) + n-22d , with probability at least 0.99 gives a (1 + ")-approximation for the geometric network surviv-ability problem with rv 2 f0; 1; 2g for any v 2 V. This algorithm can be derandomized in polynomial-time.

Applications 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)