文献类型：期刊文献

英文题名：A note on approximation algorithms of the clustered traveling salesman problem

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

机构：[1]Shanghai Ocean Univ, Coll Informat Technol, Shanghai 201306, Peoples R China;[2]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China;[3]Jiangxi Univ Finance & Econ, Sch Informat Technol, Nanchang 330013, Jiangxi, Peoples R China

年份：2017

卷号：127

起止页码：54

外文期刊名：INFORMATION PROCESSING LETTERS

收录：;EI(收录号：20172903960081);WOS:【SCI-EXPANDED(收录号:WOS:000409286600011)】；

基金：The authors are grateful to the anonymous reviewers for their helpful comments. This research is supported by the National Natural Science Foundation of China under grant numbers 11301184 and 11626120.

语种：英文

外文关键词：Traveling salesman problem; Clustered traveling salesman problem; Approximation algorithms

摘要：In an earlier paper (Bao and Liu [1]), we considered a version of the clustered traveling salesman problem (CTSP), in which both the starting and ending vertex of each cluster are free to be selected, and proposed a 2.167-approximation algorithm. In this note, we first improve this approximation ratio to 1.9 by introducing a new method to define the inter node lengths for all the nodes in Step 2 of Algorithm A of Bao and Liu [1]. Based on the above method, we then provide a 2,5-approximation algorithm for another version of CTSP where the starting vertex of each cluster is given while the ending vertex is free to be selected, which improves the previous approximation ratio of 2.643 of Guttmann-Beck et al. [5]. (C) 2017 Elsevier B.V. All rights reserved.