کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10524007 | 957181 | 2005 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved upper bound for the TSP in cubic 3-edge-connected graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We consider the travelling salesman problem (TSP) problem on (the metric completion of) 3-edge-connected cubic graphs. These graphs are interesting because of the connection between their optimal solutions and the subtour elimination LP relaxation. Our main result is an approximation algorithm better than the 3/2-approximation algorithm for TSP in general.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 33, Issue 5, September 2005, Pages 467-474
Journal: Operations Research Letters - Volume 33, Issue 5, September 2005, Pages 467-474
نویسندگان
David Gamarnik, Moshe Lewenstein, Maxim Sviridenko,