Study On Approximation Algorithms For The Min-max Clustered K-traveling Salesmen Problems

The traveling salesman problem(TSP)is a classic combinatorial optimization problem in computer science and operations research,with widespread applications in various fields.The min max cluster TSP(MMCTSP)is a generalized variant of the TSP,which can simulate more complex practical problems and has even broader practical applications.As the TSP is an NP-hard problem,the MMCTSP is also an NP-hard problem.There are mainly three research methods for tackling NP-hard problems in literature,including exact algorithms,intelligent algorithms,and approximation algorithms.This paper mainly investigates the MMCTSP from the perspective of approximation algorithms and presents an approximation algorithm with a good approximation ratio.The main research results are as follows:The first problem studied in this paper is the MMCTSP with the same starting point.Given a complete undirected graph G=(V,E),where V represents the vertex set and E represents the edge set,the vertex set V is partitioned into K subsets,each of which is called a cluster.Each edge in E,e(?)E is associated with a weight w(e).Given k traveling salesmen,the problem is to calculate k tours that all start from a common starting point,pass through all vertices in V,and consecutively go through all vertices in each cluster.The objective of the problem is to minimize the weight of the maximum tour.For this problem,this paper presents an approximation algorithm with an approximation ratio of (?)ρ_R+2ρ_P+1-1/k(?),where ρ_R represents the approximation ratio for the rural postman problem,and ρ_P represents the approximation ratio for the TSP.The basic idea of the algorithm is to first calculate a feasible tour for the corresponding clustering TSP problem and then tear it into k subpaths with equal weights.Finally,by connecting the two endpoints of each subpath to the common starting point,a feasible solution to the MMCTSP with the same starting point can be obtained.The second problem studied in this paper is the MMCTSP with arbitrary starting points.Compared with the first problem,this problem does not assume a common starting point for all tours.Specifically,the problem is to calculate k tours that pass through all vertices and satisfy the constraint that all vertices in each cluster must be visited consecutively.For this problem,this paper presents an approximation algorithm with an approximation ratio of (4ρ_P+8ρ_R-2),where ρ_R and ρ_P represent the approximation ratios for the rural postman problem and the TSP,respectively.The basic idea of the algorithm is to first provide a guess of the optimal value λ for a given instance of the problem.Then,a solving algorithm is designed for this value λ,which either returns a feasible solution with an objective function value no more than (4ρ_P+8ρ_R-2),or returns a guess value smaller than the optimal value.By conducting binary search within an interval[0,w(G)],the smallest guess value λ~* satisfying the upper bound constraint is found,and thus a feasible solution satisfying the required approximation ratio for the MMCTSP with arbitrary starting points can be obtained.