Approximation Algorithms For Some Graph Routing Problems

Graph routing problem is a hot topic in computer science and combina-torial optimization.Recently,many researchers have studied the generalized variants of Traveling Salesman Problem.In this thesis,we mainly study two generalizations of the well-known travelling salesman problem.The first one is prize-collecting cluster salesman problem,in this problem,let G=(V,E)be a complete undirected graph with vertex set V,edge set E,and edge cost c(e)satisfying triangle inequality.The vertex set V is partitioned into k clusters and in each cluster Ci the starting vertex si and ending vertex ti are specified.With each cluster Ci there is a nonnegative penalty ?i.The goal is to find a tour that visits a subset of the clusters such that the length of the tour plus the sum of the penalties of these clusters not in the tour is as small as possible,for this problem,we give a 25/6-approximation algorithm.The second problem is the cluster general routing problem,in this problem,let G=(V,E)be a.complete undirected graph with vertex set V and edge set E.The vertex set is partitioned into clusters C1,...,Ck,V'(?)V and E'(?)E are required vertex subset and required edge subset,respectively.Associated with each edge e ? E,there is a cost 1(e),which is assumed to satisfy the triangle inequality.The goal is to find a tour that visits vertices in a required subset V '(?)V exactly once and covers edges in a required subset E'(?)E at least once such that the edge cost is as small as possible.In this problem,every cluster can be visited exactly once.For this problem,depending on whether or not the starting and ending vertices of a cluster have been specified,we divide the problem into two cases.If every cluster has the specified vertices,we offer a 2.4-approximation combinatorial algorithm.If every cluster has unspecified vertices,depending on whether the required edges are incident with differen-t clusters,we consider the problem in two subcases.When all required edges are only distributed in the clusters,we get a 3.25-approximation combinatorial algorithm.For the subcase when there exist required edges incident with two different clusters,we get a 2.25-approximation combinatorial algorithm.