Simpler analysis of LP extreme points fo
β
Viswanath Nagarajan; R. Ravi; Mohit Singh
π
Article
π
2010
π
Elsevier Science
π
English
β 290 KB
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