Algorithms for the Prize-Collecting $k$-Steiner Tree Problem

In this paper, we study the prize-collecting
$k$
-Steiner tree (
$\mathsf{PC}k\mathsf{ST}$
) problem. We are given a graph
$G=(V, E)$
and an integer
$k$
. The graph is connected and undirected. A vertex
$r\in V$
called root and a subset
$R\subseteq V$
called terminals are also given. A feasible solution for the
$\mathsf{PC}k\mathsf{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 5.9672 for the
$\mathsf{PC}k\mathsf{ST}$
. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the
$k$
-Steiner tree (
$k\mathsf{ST}$
) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to 5.