Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143015 | Operations Research Letters | 2010 | 5 Pages |
Abstract
We consider the Survivable Network Design Problem (SNDP) and the Symmetric Traveling Salesman Problem (STSP). We give simpler proofs of the existence of a 12-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 12-edge in any extreme point of the set-pair LP relaxation for the element connectivitySurvivable Network Design Problem (SNDPelt).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Viswanath Nagarajan, R. Ravi, Mohit Singh,