文献类型：会议论文

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

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

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

会议论文集：21st Annual International Computing and Combinatorics Conference (COCOON)

会议日期：AUG 04-06, 2015

会议地点：Beijing, PEOPLES R CHINA

语种：英文

外文关键词：Vehicle routing; Cycle cover; Traveling salesman problem; Approximation algorithm

摘要：Given an undirected weighted graph G = (V, E), a set {C-1, C-2, CO of cycles is called a cycle cover of the vertex subset V' if V' subset of U-i=1(k) V(C-i) 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 lambda 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 14/3-approximation algorithm that has the same time complexity as the previous best 5-approximation algorithm. Moreover, we transform a p-approximation algorithm for TSP into approximation algorithms for MMCCP, RMMCCP and MCCP with ratios 4 rho, 4 rho + 1 and 4 rho, respectively. (C) 2016 Elsevier B.V. All rights reserved.