کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952421 | 1442031 | 2016 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved approximation algorithms for some min-max and minimum cycle cover problems
ترجمه فارسی عنوان
الگوریتم های تقریبی بهبود یافته برای برخی از مسائل مربوط به حداقل مینیمم و حداقل پوشش چرخه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مسیریابی خودرو، پوشش چرخه، مشکل فروشنده مسافرتی الگوریتم تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Given an undirected weighted graph G=(V,E), a set {C1,C2,â¦,Ck} of cycles is called a cycle cover of the vertex subset Vâ² if Vâ²ââªi=1kV(Ci) and its cost is given by the maximum weight of the cycles. The Min-Max Cycle Cover Problem (MMCCP) is to find a minimum cost cycle cover of V with at most k cycles. The Rooted Min-Max Cycle Cover Problem (RMMCCP) is to find a minimum cost cycle cover of VâD with at most k cycles, each of which contains one vertex in D. The Minimum Cycle Cover Problem (MCCP) aims to find a cycle cover of V of cost at most λ with the minimum number of cycles. We propose approximation algorithms for MMCCP and RMMCCP with performance ratios 5 and 6, respectively. These results improve the previous algorithms in term of both approximation ratios and running times. For MCCP we obtain a 143-approximation algorithm that has the same time complexity as the previous best 5-approximation algorithm. Moreover, we transform a Ï-approximation algorithm for TSP into approximation algorithms for MMCCP, RMMCCP and MCCP with ratios 4Ï, 4Ï+1 and 4Ï, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 45-58
Journal: Theoretical Computer Science - Volume 654, 22 November 2016, Pages 45-58
نویسندگان
Wei Yu, Zhaohui Liu,