Algorithms for the Prize-Collecting k-Steiner Tree Problem

In this paper, we study the prize-collecting $k$-Steiner tree (PC $k$ST) problem. We are given a graph $G\mathrm{=}\mathrm{(}V\mathrm{,}E\mathrm{)}$ and an integer $k$. The graph is connected and undirected. A vertex $r\mathrm{\in }V$ called root and a subset $R\mathrm{\subseteq }V$ called terminals are also given. A feasible solution for the PC $k$ST is a tree $F$ rooted at $r$ and connecting at least $k$ vertices in $R$. Excluding a vertex from the tree incurs a penalty cost, and including an edge in the tree incurs an edge cost. We wish to find a feasible solution with minimum total cost. The total cost of a tree $F$ is the sum of the edge costs of the edges in $F$ and the penalty costs of the vertices not in $F$. We present a simple approximation algorithm with the ratio of $\mathrm{5.9672}$ for the PC $k$ST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the $k$-Steiner tree ( $k$ST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to $\mathrm{5}$.