Approximation algorithms for the min-max clustered k-traveling salesmen problems.

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 C k -TSP) 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 5.5 and 16, respectively. • We consider the min-max clustered k-traveling salesmen problem. • We propose a 5.5-approximation algorithm for the case in which all the k tours have a common predefined starting vertex. • We provide a 16-approximation algorithm for the case in which no starting vertex of any tour is specified. • Both algorithms are the first constant-factor approximation algorithms. [ABSTRACT FROM AUTHOR]