Survivable Network, 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...
Main Authors: | Goemans, Michel X., Bertsimas, Dimitris J. |
---|---|
Format: | Working Paper |
Language: | en_US |
Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
Online Access: | http://hdl.handle.net/1721.1/5175 |
Similar Items
-
Survivable Networks, Linear Programming Relaxations and the Parsimonious Property
by: Goemans, Michel X., et al.
Published: (2004) -
Probabilistic analysis of the 1-tree relaxation for the Eculidean traveling salesman problem
by: Goemans, Michel X., et al.
Published: (2009) -
Analysis of Linear Programming Relaxations for a Class of Connectivity Problems
by: Goemans, Michel X.
Published: (2004) -
Analysis of linear programming relaxations for a class of connectivity problems
by: Goemans, Michel X. (Michel Xavier)
Published: (2005) -
The parsimonious property of cut covering problems and its applications
by: Bertsimas, Dimitris, et al.
Published: (2009)