A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph $$G = (V, E)$$ and a set of vertex sets $${\mathcal {V}} = \{V_1, V_2,\cdots , V_{l}\}$$ . Every edge in E has a nonnegative cost, and every vertex set in $${\mathcal {V}}$$ has a nonnegative penalty cost. For a given edge set $$F\subseteq E$$ , vertex set $$V_i\in {\mathcal {V}}$$ is said to be connected by edge set F if $$V_i$$ is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method.