文献类型：期刊文献

英文题名：New approximation algorithms for the minimum cycle cover problem

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

机构：[1] Department of Mathematics, East China University of Science and Technology, Shanghai, 200237, China; [2] College of Information Technology, Shanghai Ocean University, Shanghai, 201306, China

年份：2018

卷号：10823 LNCS

起止页码：81

外文期刊名：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

收录：EI(收录号：20182005184514)

语种：英文

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

摘要：Given an undirected weighted graph G = (V,E) with nonnegative weight function obeying the triangle inequality, a set (formula presented) of cycles is called a cycle cover if (formula presented) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most λ with the minimum number of cycles. An O(n2) 24/5-approximation algorithm and an O(n5) 14/3-approximation algorithm are given by Yu and Liu (Theor Comput Sci 654:45–58, 2016). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Then we give a new O(n3) approximation algorithm that achieves the same ratio 14/3 and has much simpler proof on the approximation ratio. Moreover, we derive an improved 32/7-approximation algorithm that runs in O(n5). ? 2018, Springer International Publishing AG, part of Springer Nature.