کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142836 | 957166 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We consider an APX-hard variant (Î-Max-ATSP) and an APX-hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a 3140-approximation algorithm for Î-Max-ATSPÂ and a 34-approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Letters - Volume 37, Issue 3, May 2009, Pages 176-180
Journal: Operations Research Letters - Volume 37, Issue 3, May 2009, Pages 176-180
نویسندگان
Markus Bläser, L. Shankar Ram, Maxim Sviridenko,