Approximation Algorithms For Problems Related To The Node-weighted Generalized Steiner Forest Problem

In this paper,we study approximation algorithms for the node-weighted generalized Steiner forest problem in planar graphs and the node-weighted prize-collecting generalized Steiner forest problem.In the node-weighted generalized Steiner forest problem in planar graphs,we are given a planar graph G=(V,E),where each vertex is associated with a nonnegative cost.Assume that L=｛V1,V2,…,Vh},where these Vi called demands are vertex subsets of V with size at least 2.The goal is to find a minimum cost vertex subset such that each demand Vi∈L is connected by this vertex subset.Firstly,we present the integral program,the relaxed linear program and its dual program.Based on the dual program we design an approximation algorithm for this problem.In addition,we give an upper bound for the number of the edges between a feasible augmentation of a partial solution X and the violated connected component of X,and further we obtain the approximation ratio of this algorithm is 6.In the node-weighted prize-collecting generalized Steiner forest problem,we are given a graph G=(V,E)together with the demand set L=｛V1,V2,…,Vh},where these Vi called demands are vertex subsets of V with size at least 2.Assume that each vertex is associated with a nonnegative cost and each demand is associated with a nonnegative penalty cost.The goal is to find a vertex subset such that the total cost,including the vertex cost in this vertex subset and the penalty cost of the demands not connected by this vertex subset,is minimized.For the node-weighted prize-collecting generalized Steiner forest problem,Firstly,we present the integral program,the relaxed linear program,the corresponding dual program and a simplified dual program.By constructing a dual vector called disk and discussing the properties of the disks,we design an approximation algorithm for this problem based on the simplified dual program.Moreover,we give an upper bound for the cost including that for the vertices chosen and that for the demands penalized in each iteration.At last,we obtain that the approximation ratio of the algorithm is qH|τ|,where q=max{|Vj|:Vj∈L},T=Ui∈[h]Vi,and H|T| is the |T|-th harmonic number.