کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142430 | 957148 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the integrality ratio of the subtour LP for Euclidean TSP
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/34/3. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was 8/78/7. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 42, Issue 8, December 2014, Pages 495–499
Journal: Operations Research Letters - Volume 42, Issue 8, December 2014, Pages 495–499
نویسندگان
Stefan Hougardy,