文献类型：期刊文献

英文题名：Approximation algorithms for the min-max clustered k-traveling salesmen problems

作者：Bao, Xiaoguang[1];Xu, Lei[1];Yu, Wei[2];Song, Wei[1]

机构：[1]Shanghai Ocean Univ, Coll Informat Technol, Shanghai 201306, Peoples R China;[2]East China Univ Sci & Technol, Sch Math, Shanghai 200237, Peoples R China

年份：2022

卷号：933

起止页码：60

外文期刊名：THEORETICAL COMPUTER SCIENCE

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

基金：The authors are grateful to the anonymous referees for their valuable comments and suggestions. This research is supported by the National Natural Science Foundation of China under grant number 11701363 and the Natural Science Foundation of Shanghai under grant number 19ZR1411800.

语种：英文

外文关键词：Approximation algorithm; Min-max; Traveling salesman problem; Clustered traveling salesman problem

摘要：Given a complete undirected graph G = (V, E), where V is the vertex set partitioned into K clusters V-1, V-2,...,V-K and E is the edge set with edge weights satisfying triangle inequality, and a positive integer k, the min-max clustered k-traveling salesmen problem(min-max Ck-TSP) asks to find a set of ktours to visit all vertices, such that each cluster is visited by exactly one tour and the vertices of each cluster are visited consecutively. The objective is to minimize the weight of the maximum weight tour. The problem is known to be NP-hard even when k = 1 and K = 1. In this paper, we consider two variants of the problem. The first one is all the ktours have a common predefined starting vertex, and the other one is no starting vertex of any tour is specified. For both the variants we propose the first constant-factor approximation algorithms with ratios 5.5 and 16, respectively. (c) 2022 Elsevier B.V. All rights reserved.