Survivable networks, linear programming relaxations and the parsimonious property

The authors 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-edge-connected network design problem. The authors 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, they derive various structural properties of these LP relaxations, the authors present some algorithmic improvements and the authors perform tight worst-case analyses of two heuristics for the survivable network design problem.