✦ LIBER ✦
Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
✍ Scribed by Viswanath Nagarajan; R. Ravi; Mohit Singh
- Publisher
- Elsevier Science
- Year
- 2010
- Tongue
- English
- Weight
- 290 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0167-6377
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the Survivable Network Design Problem (SNDP) and the Symmetric Traveling Salesman Problem (STSP). We give simpler proofs of the existence of a 1 2 -edge and 1-edge in any extreme point of the natural LP relaxations for the SNDP and STSP, respectively. We formulate a common generalization of both problems and show our results by a new counting argument. We also obtain a simpler proof of the existence of a 1 2 -edge in any extreme point of the set-pair LP relaxation for the element connectivity Survivable Network Design Problem (SNDP elt ).