Abstract: 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₁, V₂, · · ·, V_l}. Assume c:E → $\mathbb{R}$⁺ is an edge cost function and π:2^V → $\mathbb{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 V_i not connected by F is minimized. By using the primal-dual technique, we give a 3-approximation algorithm for this problem.

Key words: Generalized prize-collecting Steiner forest problem, Submodular function, Primal-dual algorithm