Approximation Algorithm for Unrooted Prize-Collecting Forest with Multiple Components and Its Application on Prize-Collecting Sweep Coverage

In this paper, we present a polynomial time 2-approximation algorithm for the {\em unrooted prize-collecting forest with $K$ components} (URPCF$_K$) problem, the goal of which is to find a forest with exactly $K$ connected components to minimize the weight of the forest plus the penalty incurred by the vertices not spanned by the forest. For its rooted version RPCF$_K$, a 2-approximation algorithm is known. For the unrooted version, transforming it into a rooted version by guessing roots runs in time exponentially depending on $K$, which is unacceptable when $K$ is not a constant. We conquer this challenge by designing a rootless growing plus rootless pruning algorithm. As an application, we make use of this algorithm to solve the {\em prize-collecting min-sensor sweep cover} problem, improving previous approximation ratio 8 to 5. Keywords: approximation algorithm, prize-collecting Steiner forest, sweep cover.