SURVIVABLE NETWORKS, LINEAR-PROGRAMMING RELAXATIONS AND THE PARSIMONIOUS PROPERTY

We consider the survivable network design problem - the problem of des igning, 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 desig n problem. We establish a property, referred to as the parsimonious pr operty, of the linear programming (LP) relaxation of a classical formu lation for the problem. The parsimonious property has numerous consequ ences. For example, we derive various structural properties of these L P relaxations, we present some algorithmic improvements and we perform tight worst-case analyses of two heuristics for the survivable networ k design problem.