کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1143015 | 957173 | 2010 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simpler analysis of LP extreme points for traveling salesman and survivable network design problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Simpler analysis of LP extreme points for traveling salesman and survivable network design problems Simpler analysis of LP extreme points for traveling salesman and survivable network design problems](/preview/png/1143015.png)
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 38, Issue 3, May 2010, Pages 156–160
Journal: Operations Research Letters - Volume 38, Issue 3, May 2010, Pages 156–160
نویسندگان
Viswanath Nagarajan, R. Ravi, Mohit Singh,