4551
правка
Минимальные k-связные геометрические сети: различия между версиями
Перейти к навигации
Перейти к поиску
Минимальные k-связные геометрические сети (посмотреть исходный код)
Версия от 01:02, 9 сентября 2016
, 9 сентября 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 42: | Строка 42: | ||
В более общей формулировке задач о многосвязности в графах следует учитывать ограничения неоднородной связности. | В более общей формулировке задач о многосвязности в графах следует учитывать ограничения неоднородной связности. | ||
Задача конструирования сети с повышенной живучестью | |||
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) | |||