文献类型：期刊文献

英文题名：Approximation Algorithms for the Min-Max $K$-Clustered Traveling Salesmen Problems

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

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

年份：2022

外文期刊名：SSRN

收录：EI(收录号：20220066419)

语种：英文

外文关键词：Traveling salesman problem - Undirected graphs

摘要：Given a complete undirected graph $G=(V,E)$, where $V$ is the vertex set partitioned into $K$ \emph{clusters} $V_1,V_2,\dots,V_K$ and $E$ is the edge set with edge weights satisfying triangle inequality, and a positive integer $k$\, the min-max $k$-clustered traveling salesmen problem (min-max $k$-CTSP) asks to find a set of $k$ tours 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 $k$ tours 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 $(\rho_R+2\rho_P+1-\frac{1}{k})$ and $(8\rho_R+4\rho_P-2)$ respectively, where $\rho_R$ and $\rho_P$ are the approximation ratios available for the \emph{rural postman problem} (RPP) and the \emph{traveling salesman path problem} (TSPP), respectively. ? 2022, The Authors. All rights reserved.