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(GPCSF-SP problem).In this problem,we are given an undirected connected graph G=(V,E)and a collection of disjoint vertex subsets V={V_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→R_(+)is a submodular penalty function.The objective of the GPCSF-SP problem 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 S containing these Vi not connected by F is minimized.By using the primal-dual technique,we give a 3-approximation algorithm for this problem.