文献类型：期刊文献

英文题名：Improved approximation algorithms for min-max and minimum vehicle routing problems

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

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

年份：2015

卷号：9198

起止页码：147

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

收录：EI(收录号：20155201722774)

语种：英文

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

摘要：Given an undirected weighted graph G = (V,E), a set C1, C2, . . . , Ck of cycles is called a cycle cover of V′ if V′ ? ∪ki=1V(Ci) and its cost is 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 and each cycle contains one vertex in D. The Minimum Cycle Cover Problem(MCCP) aims to find a cycle cover of V of cost at most λ with minimum number of cycles. We propose approximation algorithms for the MMCCP, RMCCP and MCCP with ratios 5, 6 and 24/5, respectively. Our results improve the previous algorithms in term of both approximation ratios and running times. Moreover, we transform a ρ-approximation algorithm for the TSP into approximation algorithms for the MMCCP, RMCCP and MCCP with ratios 4ρ, 4ρ + 1 and 4ρ, respectively. ? Springer International Publishing Switzerland 2015.