Return to search

Survivable Networks, Linear Programming Relaxations and the Parsimonious Property

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 the k-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 worstcase analyses of two heuristics for the survivable network design problem.

Identiferoai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/5217
Date06 1900
CreatorsGoemans, Michel X., Bertsimas, Dimitris J.
PublisherMassachusetts Institute of Technology, Operations Research Center
Source SetsM.I.T. Theses and Dissertation
Languageen_US
Detected LanguageEnglish
TypeWorking Paper
Format1615087 bytes, application/pdf
RelationOperations Research Center Working Paper;OR 225-90

Page generated in 0.0021 seconds