Approximation Algorithms For The Clustered Path Traveling Salesman Problem And The Group Prize-Collecting Traveling Salesman Problem With Submodular Penalties

The traveling salesman problem is a classical NP-hard problem in combinatorial optimization.In this thesis,we study two variants of traveling salesman problem:the group prize-collecting traveling salesman problem with submodular penalties and the clustered path traveling salesman problem.For the group prize-collecting traveling salesman problem with submodular penal-ties,we first use the given example of the group prize-collecting traveling salesman prob-lem with submodular penalties to construct an example of the prize-collecting traveling salesman problem with submodular penalties,by defining appropriate cost function and submodular penalty function.Then,we convert the output solution of the existing ap-proximation algorithm of the prize-collecting traveling salesman problem with submod-ular penalties into the solution of the group prize-collecting traveling salesman problem with submodular penalties,and design the approximation algorithm for the group prize-collecting traveling salesman problem with submodular penalties.Finally,we analyze the approximation algorithm,and the approximation ratio is 2k I,where k is the number of groups,I is the cardinality of the largest group.For the clustered path traveling salesman problem,we divide into four cases.Firstly,we design the approximation algorithms of the path stacker crane problem and the path rural postman problem,which are subproblems for solving the clustered path traveling salesman problem.Then,based on these subproblems that can be solved,and using the approximation algorithm of the path traveling salesman problem,we design approxima-tion algorithms for the clustered path traveling salesman problem in the four cases,and the approximation ratios are 8/3,2,8/3,13/4,respectively.