کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1142430 957148 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the integrality ratio of the subtour LP for Euclidean TSP
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On the integrality ratio of the subtour LP for Euclidean TSP
چکیده انگلیسی

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
نویسندگان
,