کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1143322 | 957191 | 2011 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An analysis of the extended Christofides heuristic for the k-depot TSP
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An analysis of the extended Christofides heuristic for the k-depot TSP An analysis of the extended Christofides heuristic for the k-depot TSP](/preview/png/1143322.png)
چکیده انگلیسی
We study an extension of the classical traveling salesman problem (TSP) to a situation with kâ¥2 depots at each of which a distinct salesman is based. We show that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2â1/k, which improves on the known 2-approximation algorithm from the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 39, Issue 3, May 2011, Pages 218-223
Journal: Operations Research Letters - Volume 39, Issue 3, May 2011, Pages 218-223
نویسندگان
Zhou Xu, Liang Xu, Brian Rodrigues,