文献类型：期刊文献

英文题名：Improved approximation algorithms for some min-max and minimum cycle cover problems

作者：Yu, Wei[1]; Liu, Zhaohui[1]

机构：[1] Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, China

年份：2016

卷号：654

起止页码：45

外文期刊名：Theoretical Computer Science

收录：EI(收录号：20160701945211)

语种：英文

外文关键词：Costs - Undirected graphs - Routing algorithms - Traveling salesman problem - Vehicle routing

摘要：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 [formula presented]-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. ? 2016 Elsevier B.V.