Approximation Algorithms For The Partial Generalized Steiner Forest Problem

The Steiner tree problem and Steiner forest problem are classical NP-hard problems in combinatorial optimization.In this thesis,we study one variant of Steiner forest problem:the partial generalized Steiner forest problem.In the partial generalized Steiner forest problem,given a connected graph G=(V,E)with non-negative costs ce for the edges e ? E,a family of disjoint vertex sets V={V1,V2,…,Vl} and a positive integer k ?l.The goal is to find a minimum-cost edge subset F such that at least k of the vertex sets in V are connected by F.We mainly designs two approximate algorithms for the partial generalized Steiner forest problem.The first one is a primal-dual algorithm based on the resource augmentation,and the cost of the edge subset F output by the algorithm is at most 16/?2 times the cost of an optimal algorithm that removes at most[(1-?)(l-k)J vertex sets,where? is any constant with 0<?<1.The second one is based on a mixed strategy of LP-rounding and greedy approach,and its approximation ratio is O((?)).