W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
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.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
Michael E. Henderson
International Journal of Bifurcation and Chaos in Applied Sciences and Engineering
Joy Y. Cheng, Daniel P. Sanders, et al.
SPIE Advanced Lithography 2008
Charles Micchelli
Journal of Approximation Theory