Exact And Approximation Algorithms For Some Variants Of The Min-Max K-traveling Salesmen Problem On A Tree

Given an edge-weighted tree T=(V,E)with a depot s ?V and k identical salesmen,where k is independent of the input,the minmax k-traveling salesmen problem on a tree(Min-Max k-TSPT)is to find a set of k tours,each of which starting from and ending at s,for the salesmen to serve all customers located at the vertices of the tree such that the maximum total edge weight of the tours is minimized.In this paper,we present new simplified pseudo-polynomial time exact algorithms for both the Min-Max k-TSPT and its multi-depot extension,where there is a candidate depot set D ?V and each tour is required to start from and end at the same depot in D.Based on this simplified approach,we devise pseudo-polynomial algorithms for some natural variants of the Min-Max k-TSPT and their multi-depot generalization.Moreover,we transform these pseudo-polynomial algorithms into fully polynomial time approximation schemes(FPTASes)by standard rounding and scaling technique.In Chapter 1,we introduce the background and some basic concepts of this paper.We introduce the history of travelling salesman problem and some relevant achievements about this paper those other researchers have done.Chapter 2 introduces the problems and some symbols used in this paper.It also introduces the preparation of the standardization of the examples and the ordering of node numbers.In Chapter 3,we propose an improved pseudo-polynomial exact algorithm for Min-Max k-TSPT,on the base of the first algorithm,we give a pseudo-polynomial exact algorithm for Min-Max k-PCPT.In Chapter 4,we present a pseudo-polynomial exact algorithm for Multi-depot Min-Max k-TCPT and extend it to Multi-depot Min-Max k-PCPT and Multi-depot Min-Max k-CPPT.In Chapter 5,we transform pseudo-polynomial exact algorithms above into fully polynomial time approximation schemes by standard rounding and scaling technique.In Chapter 6,we summarize this paper and point out the possible direction of future research based on this paper.