文献类型：会议论文

英文题名：Improved Approximation Algorithms for Min-Max and Minimum Vehicle Routing Problems

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

机构：[1]E 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, ... , C-k of cycles is called a cycle cover of V' if V' subset of boolean OR(k)(i=1) V (C-i) 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 lambda 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 rho-approximation algorithm for the TSP into approximation algorithms for the MMCCP, RMCCP and MCCP with ratios 4 rho, 4 rho + 1 and 4 rho, respectively.