Abstract
We consider the survivable network design problem — the problem of designing, at minimum cost, a network with edge-connectivity requirements. As special cases, this problem encompasses the Steiner tree problem, the traveling salesman problem and thek-edge-connected network design problem. We establish a property, referred to as the parsimonious property, of the linear programming (LP) relaxation of a classical formulation for the problem. The parsimonious property has numerous consequences. For example, we derive various structural properties of these LP relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable network design problem.
Similar content being viewed by others
References
A. Agrawal, P. Klein and R. Ravi, “When trees collide: An approximation algorithm for the generalized Steiner problem in networks,” in:Proceedings of the 23rd ACM Symposium on Theory of Computing (1991) pp. 134–144.
Y.P. Aneja, “An integer linear programming approach to the Steiner problem in graphs,”Networks 10 (1980) 167–178.
A. Balakrishnan, T.L. Magnanti and R.T. Wong, “A dual-ascent procedure for large-scale uncapacitated network design,”Operations Research 37 (1989) 716–740.
E. Balas and P. Toth, “Branch and Bound methods,” in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985) pp. 361–401.
D. Bienstock, M.X. Goemans, D. Simchi-Levi and D.P. Williamson, “A note on the prize collecting traveling salesman problem,”Mathematical Programming 59 (1993) 413–420.
N. Christofides, “Worst-case analysis of a new heuristic for the traveling salesman problem,” Technical Report, GSIA, Carnegie-Mellon University (Pittsburgh, PA, 1976).
G. Cornuejols, M.L. Fisher and G.L. Nemhauser, “Location of bank accounts to optimize float,”Management Science 23 (1977) 789–810.
J. Edmonds, “Maximum matching and a polyhedron with 0–1 vertices,”Journal of Research of the National Bureau of Standards 69B (1965) 125–130.
J. Edmonds, “Submodular functions, matroids and certain polyhedra,” in: R. Guy et al., eds.,Combinatorial Structures and their Applications (Gordon and Breach, London, 1970), pp. 69–87.
C. El-Arbi, “Une heuristique pour le problème de l'arbre de Steiner,”RAIRO Operations Research 12 (1978) 207–212.
H. Frank and I.T. Frisch,Communication, Transmission and Transportation Networks (Addison-Wesley, Reading, MA, 1971).
M.X. Goemans and D. Bertsimas, “Probabilistic analysis of the Held and Karp lower bound for the Euclidean traveling salesman problem,”Mathematics of Operations Research 16 (1991) 72–89.
M.X. Goemans and D.P. Williamson, “A general approximation technique for constrained forest problems,” in:Proceedings of the third ACM-SIAM Symposium on Discrete Algorithms (1992) pp. 307–315.
R.E. Gomory and T.C. Hu, “Synthesis of a communication network,”SIAM Journal on Applied Mathematics 9 (1961) 551–570.
M. Held and R.M. Karp, “The traveling-salesman problem and minimum spanning trees,”Operations Research 18 (1970) 1138–1162.
M. Held and R.M. Karp, “The traveling salesman problem and minimum spanning trees: Part II,”Mathematical Programming 1 (1971) 6–25.
D. Johnson, talk presented at theMathematical Programming Symposium, Tokyo (1988).
D. Johnson, personal communication (1989).
R.M. Karp, “Reducibility among combinatorial problems”, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of Computer Computations (Plenum, New York, 1972) pp. 85–103.
R.M. Karp, “Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane,”Mathematics of Operations Research 2 (1977) 209–224.
L. Kou, G. Markowsky and L. Berman, “A fast algorithm for Steiner trees,”Acta Informatica 15 (1981) 141–145.
J.B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem,”Proceedings of the American Mathematical Society 7 (1956) 48–50.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985).
L. Lovász, “On some connectivity properties of Eulerian graphs,”Acta Mathematica Academiae Scientiarum Hungaricae 28 (1976) 129–138.
N. Maculan, “The Steiner problem in graphs,”Annals of Discrete Mathematics 31 (1987) 185–212.
K. Mehlhorn, “A faster approximation algorithm for the Steiner problem in graphs,”Information Processing Letters 27 (1988) 125–128.
C.L. Monma and C.-W. Ko, “Methods for designing survivable communication networks,” NATO Advanced Research Workshop (Denmark, 1989).
C.L. Monma, B.S. Munson and W.R. Pulleyblank, “Minimum weight two-connected spanning networks,”Mathematical Programming 46 (1990) 153–171.
C.L. Monma and D.F. Shallcross, “Methods for designing communication networks with certain two-connected survivability constraints,”Operations Research 37 (1989) 531–541.
J. Plesnik, “A bound for the Steiner tree problem in graphs,”Mathematica Slovaca 31 (1981) 155–163.
R.C. Prim, “Shortest connection networks and some generalizations,”The Bell System Technical Journal 36 (1957) 1389–1401.
S. Sahni and T. Gonzalez, “P-complete approximation problems,”Journal of the Association for Computing Machinery 23 (1976) 555–565.
D. Shmoys and D. Williamson, “Analyzing the Held-Karp TSP bound: A monotonicity property with application,”Information Processing Letters 35 (1990) 281–285.
S. Sridhar and R. Chandrasekaran, “Integer solution to synthesis of communication network,” Technical Report, The University of Texas (Dallas, TX, 1989).
K. Steiglitz, P. Weiner and D.J. Kleitman, “The design of minimum-cost survivable networks,”IEEE Transactions on Circuit Theory CT-16(4) (1969) 455–460.
H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,”Mathematica Japonica 24 (1980) 573–577.
P. Winter, “Steiner problem in networks: a survey,”Networks 17 (1987) 129–167.
L.A. Wolsey, “Heuristic analysis, linear programming and Branch and Bound,”Mathematical Programming Study 13 (1980) 121–134.
R.T. Wong, “A dual ascent approach for Steiner tree problems on a directed graph,”Mathematical Programming 28 (1984) 271–287.
Author information
Authors and Affiliations
Additional information
The research of both authors was partially supported by the National Science Foundation under grant ECS-8717970 and the Leaders for manufacturing program at MIT.
Rights and permissions
About this article
Cite this article
Goemans, M.X., Bertsimas, D.J. Survivable networks, linear programming relaxations and the parsimonious property. Mathematical Programming 60, 145–166 (1993). https://doi.org/10.1007/BF01580607
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580607