×

zbMATH — the first resource for mathematics

Approximating minimum size {1,2}-connected networks. (English) Zbl 1011.68178
Summary: The problem of finding the minimum size 2-connected subgraph is a classical problem in network design. It is known to be NP-hard even on cubic planar graphs and MAX SNP-hard. We study the generalization of this problem, where requirements of 1 or 2 edge or vertex disjoint paths are specified between every pair of vertices, and the aim is to find a minimum size subgraph satisfying these requirements. For both problems we give \(\frac {3}{2}\)-approximation algorithms. This improves on the straightforward 2-approximation algorithms for these problems, and generalizes earlier results for 2-connectivity. We also give analyses of the classical local optimization heuristics for these two network design problems.
MSC:
68W25 Approximation algorithms
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] E. Aarts, J.K. Lenstra (Eds.), Local Search in Combinatorial Optimization, Wiley, Chichester, 1997. · Zbl 0869.00019
[2] J. Cheriyan, A. Sebő, Z. Szigeti, An improved approximation algorithm for minimum size 2-edge connected spanning subgraphs, in: Proceedings of the Sixth International Integer Programming and Combinatorial Optimization Conference IPCO, Lecture Notes in Computer Science, eds. R.E. Bixby, E.A. Boyd and R.Z. Rı́os-Mercado, Vol. 1412, Springer, Berlin, 1998, pp. 126-136.
[3] C.G. Fernandes, A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem, J. Algorithms 28 (1998) 105-124; Preliminary version in Proceedings of the Eighth Annual ACM-SIAM SODA, 1997. · Zbl 0919.68096
[4] L. Fleischer, A 2-approximation for minimum cost 0,1,2 vertex connectivity, in: Proceedings of the Eighth International Integer Programming and Combinatorial Optimization Conference IPCO, Lecture Notes in Computer Science, eds. K. Aardal and B. Gerards, Vol. 2081, Springer, Berlin, 2001, pp. 115-129. · Zbl 1010.90518
[5] N. Garg, V. Santosh, A. Singla, Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques, in: Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, New York, 1993, pp. 103-111. · Zbl 0801.68126
[6] M.X. Goemans, A. Goldberg, S. Plotkin, D.B. Shmoys, È. Tardos, D.P. Williamson, Improved approximation algorithms for network design problems, in: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, New York, 1994, pp. 223-232. · Zbl 0873.68005
[7] M. Grötschel, C. Monma, M. Stoer, Design of survivable networks, in: Handbook in Operations Research and Management Science, Volume on Networks, eds. M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser, North-Holland, Amsterdam, 1995.
[8] K. Jain, A factor 2 approximation algorithm for the generalized steiner network problem, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, New York, 1998, pp. 292-301.
[9] S. Khuller, U. Vishkin, Biconnectivity approximations and graph carvings, J. ACM 41(2) (1994) 214-235; Preliminary version in Proceedings of the 24th Annual ACM STOC, 1992. · Zbl 0822.68082
[10] P. Krysta, V.S. Anil Kumar, Approximation algorithms for minimum size 2-connectivity problems, in: Proceedings of the 18th International Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, eds. A. Ferreira and H. Reichel, Vol. 2010, Springer, Berlin, 2001, pp. 431-442. · Zbl 0976.68191
[11] Nagamochi, H; Ibaraki, T, A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica, 7, 583-596, (1992) · Zbl 0763.05065
[12] Z. Nutov, Approximating multiroot 3-outconnected subgraphs, in: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, New York, 1999, pp. 951-952. · Zbl 0929.68092
[13] Ravi, R; Williamson, D.P, An approximation algorithm for minimum-cost vertex-connectivity problems, Algorithmica, 18, 1, 21-43, (1997) · Zbl 0873.68076
[14] S. Vempala, A. Vetta, Factor 4/3 approximations for minimum 2-connected subgraphs, in: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX, Lecture Notes in Computer Science, eds. K. Jansen and S. Khuller, Vol. 1913, Springer, Berlin, 2000, pp. 262-273. · Zbl 0976.90114
[15] D.P. Williamson, M.X. Goemans, M. Mihail, V.V. Vazirani, A primal-dual approximation algorithm for generalized steiner network problems, Combinatorica 15 (1995) 435-454; Preliminary version in Proceedings of the 25th Annual ACM STOC, 1993. · Zbl 0838.90133
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.