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...
| Main Authors: | , |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/5217 |
| _version_ | 1826189433644253184 |
|---|---|
| author | Goemans, Michel X. Bertsimas, Dimitris J. |
| author_facet | Goemans, Michel X. Bertsimas, Dimitris J. |
| author_sort | Goemans, Michel X. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:14:55Z |
| format | Working Paper |
| id | mit-1721.1/5217 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:14:55Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/52172019-04-09T17:33:28Z Survivable Networks, Linear Programming Relaxations and the Parsimonious Property Goemans, Michel X. Bertsimas, Dimitris J. Keywords: network design, LP relaxations, worst-case analysis, heuristics. 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. 2004-05-28T19:28:34Z 2004-05-28T19:28:34Z 1990-06 Working Paper http://hdl.handle.net/1721.1/5217 en_US Operations Research Center Working Paper;OR 225-90 1615087 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Keywords: network design, LP relaxations, worst-case analysis, heuristics. Goemans, Michel X. Bertsimas, Dimitris J. Survivable Networks, Linear Programming Relaxations and the Parsimonious Property |
| title | Survivable Networks, Linear Programming Relaxations and the Parsimonious Property |
| title_full | Survivable Networks, Linear Programming Relaxations and the Parsimonious Property |
| title_fullStr | Survivable Networks, Linear Programming Relaxations and the Parsimonious Property |
| title_full_unstemmed | Survivable Networks, Linear Programming Relaxations and the Parsimonious Property |
| title_short | Survivable Networks, Linear Programming Relaxations and the Parsimonious Property |
| title_sort | survivable networks linear programming relaxations and the parsimonious property |
| topic | Keywords: network design, LP relaxations, worst-case analysis, heuristics. |
| url | http://hdl.handle.net/1721.1/5217 |
| work_keys_str_mv | AT goemansmichelx survivablenetworkslinearprogrammingrelaxationsandtheparsimoniousproperty AT bertsimasdimitrisj survivablenetworkslinearprogrammingrelaxationsandtheparsimoniousproperty |