Publication

Operations Research Letters

Paper

# Simpler analysis of LP extreme points for traveling salesman and survivable network design problems

## 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 frac(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 frac(1, 2)-edge in any extreme point of the set-pair LP relaxation for the element connectivitySurvivable Network Design Problem (SNDPe l t). © 2010 Elsevier B.V. All rights reserved.