کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418410 | 681664 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Deterministic algorithms for multi-criteria Max-TSP
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Deterministic algorithms for multi-criteria Max-TSP Deterministic algorithms for multi-criteria Max-TSP](/preview/png/418410.png)
چکیده انگلیسی
We present deterministic approximation algorithms for the multi-criteria maximum traveling salesman problem (Max-TSP). Our algorithms are faster and simpler than the existing randomized algorithms.We devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/2k−ε1/2k−ε and 1/(4k−2)−ε1/(4k−2)−ε, respectively, where kk is the number of objective functions. For two objective functions, we obtain ratios of 3/8−ε3/8−ε and 1/4−ε1/4−ε for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2277–2285
Journal: Discrete Applied Mathematics - Volume 160, Issue 15, October 2012, Pages 2277–2285
نویسندگان
Bodo Manthey,