An Approximation Algorithm For The Generalized Prize-Collecting Steiner Forest Problem With Submodular Penalties

In this paper,we consider the generalized prize-collecting Steiner forest problem with submodular penalties.In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V1,V2,…V1}.Assume c:E?R?0 is an edge cost function and ?:2v?R?0 is a submodular penalty function.For an edge subset F,a vertex subset Vi is said to be connected by F if Vi is in a connected component of the subgraph(V,F).The objective of the generalized prize-collecting Steiner forest problem with submodular penalties is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection containing these Vi not connected by F is minimized.For the above problem,we first give the integer linear program,the linear program and its corresponding dual program.Then by using the primal dual theory,we design an approximation algorithm,and prove that the algorithm runs in polynomial time.In the last,we analyze the performance of the algorithm,and obtain its approximation ratio is 3.