Approximation algorithms for network design with metric costs

ABSTRACT

We study undirected networks with edge costs that satisfy the triangle inequality. Let n denote the number of nodes. We present an O(1)-approximation algorithm for a generalization of the metric-cost subset k-node-connectivity problem. Our approximation guarantee is proved via lower bounds that apply to the simple edge-connectivity version of the problem, where the requirements are for edge-disjoint paths rather than for openly node-disjoint paths. A corollary is that, for metric costs and for each k=1,2,…,n-1, there exists a k-node connected graph whose cost is within a factor of 24 of the cost of any simple k-edge connected graph. This resolves an open question in the area. Based on our O(1)-approximation algorithm, we present an O(log rmax)-approximation algorithm for the node-connectivity survivable network design problem where rmax denotes the maximum requirement over all pairs of nodes. Our results contrast with the case of edge costs of zero or one, where Kortsarz et al. [20]recently proved, assuming NP⊈, quasi-P, a hardness-of-approximation lower bound of 2^{log 1-εn} for the subset k-node-connectivity problem, where ε denotes a small positive number.

REFERENCES

• 1: Ajit Agrawal , Philip Klein , R. Ravi, When Trees Collide: An Approximation Algorithm for theGeneralized Steiner Problem on Networks, SIAM Journal on Computing, v.24 n.3, p.440-456, June 1995 [doi>10.1137/S0097539792236237]
• 2: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 3: Marshall Bern , Paul Plassmann, The steiner problem with edge lengths 1 and 2,, Information Processing Letters, v.32 n.4, p.171-176, Sept 1, 1989 [doi>10.1016/0020-0190(89)90039-2 ]
• 4: Daniel Bienstock , Ernest F. Brickell , Clyde L. Monma, On the structure of minimum-weight k-connected spanning networks, SIAM Journal on Discrete Mathematics, v.3 n.3, p.320-329, Aug. 1990 [doi>10.1137/0403027]
• 5: J. Cheriyan, T. Jordán and Z. Nutov, "On rooted node-connectivity problems," Algorithmica, 30, 353--375, 2001.
• 6: Joseph Cheriyan , Santosh Vempala , Adrian Vetta, Approximation algorithms for minimum-cost k-vertex connected subgraphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509955]
• 7: J. Cheriyan, S. Vempala and A. Vetta, "An approximation algorithm for the minimum-cost k-vertex connected subgraph," SIAM Journal on Computing, 32, 1050--1055, 2003.
• 8: N. Christofides, "Worst case analysis of a new heuristic for the traveling salesman problem," Report 388, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, 1976.
• 9: Artur Czumaj , Andrzej Lingas, On approximability of the minimum-cost k-connected spanning subgraph problem, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.281-290, January 17-19, 1999, Baltimore, Maryland, United States
• 10: Artur Czumaj , Andrzej Lingas , Hairong Zhao, Polynomial-Time Approximation Schemes for the Euclidean Survivable Network Design Problem, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.973-984, July 08-13, 2002
• 11: G. B. Dantzig, L. R. Ford and D. R. Fulkerson, "Solution of a large-scale traveling-salesman problem," Operations Research 2, 393--410, 1954.
• 12: A. Frank, "Connectivity augmentation problems in network design," in Mathematical Programming: State of the Art 1994, (Eds. J. R. Birge and K. G. Murty, The University of Michigan, Ann Arbor, MI, 34--63, 1994.
• 13: G. L. Frederickson and J. Ja'Ja', "On the relationship between the biconnectivity augmentation and traveling salesman problems," Theor. Comp. Sci. 19, 189--201, 1982.
• 14: Michel X. Goemans , Dimitris J. Bertsimas, Survivable networks, linear programming relaxations and the parsimonious property, Mathematical Programming: Series A and B, v.60 n.2, p.145-166, June 24, 1993
• 15: M. X. Goemans , A. V. Goldberg , S. Plotkin , D. B. Shmoys , É. Tardos , D. P. Williamson, Improved approximation algorithms for network design problems, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 23-25, 1994, Arlington, Virginia, United States
• 16: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 17: Kamal Jain, A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.448, November 08-11, 1998
• 18: Samir Khuller, Approximation algorithms for finding highly connected subgraphs, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 19: Samir Khuller , Balaji Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, v.21 n.2, p.434-450, Sept. 1996 [doi>10.1006/jagm.1996.0052 ]
• 20: Guy Kortsarz , Robert Krauthgamer , James R. Lee, Hardness of Approximation for Vertex-Connectivity Network Design Problems, SIAM Journal on Computing, v.33 n.3, p.704-720, 2004 [doi>10.1137/S0097539702416736]
• 21: G. Kortsarz , Z. Nutov, Approximation algorithm for k-node connected subgraphs via critical graphs, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007381]
• 22: Guy Kortsarz , Zeev Nutov, Approximating node connectivity problems via set covers, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.194-205, September 05-08, 2000
• 23: L. Lovász, Combinatorial Problems and Exercises, North-Holland, Amsterdam, and Akadémiai Kiadć, Budapest, 1979.
• 24: C. L. Monma , B. S. Munson , W. R. Pulleyblank, Minimum-weight two-connected spanning networks, Mathematical Programming: Series A and B, v.46 n.2, p.153-171, Feb. 1990
• 25: C. L. Monma and D. F. Shallcross, "Methods for designing communication networks with certain two-connectivity survivability constraints," Operations Research 37, 531--541, 1989.
• 26: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 27: M. Stoer, Design of Survivable Networks, Lecture Notes in Mathematics 1531, Springer-Verlag, Berlin, 1992.
• 28: Luca Trevisan, When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree, SIAM Journal on Computing, v.30 n.2, p.475-485, 2000 [doi>10.1137/S0097539799352735]
• 29: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 30: D. Williamson, M. Goemans, M. Mihail and V. Vazirani, "A primal-dual approximation algorithm for generalized Steiner network problems," Combinatorica 15, 435--454, 1995.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, graph connectivity, metric costs