Abstract:

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 V = {V1, V2, · · · , Vl }.
Every edge in E has a nonnegative cost, and every vertex set in V has a nonnegative
penalty cost. For a given edge set F ⊆ E, vertex set Vi ∈ V is said to be connected by
edge set F if Vi 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.

Key words: Prize-collecting ·, Steiner forest ·, Approximation algorithm ·, Primal-dual