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