@article{Han2022, 
author = {Lu Han and Changjun Wang and Dachuan Xu and Dongmei Zhang},
title = {Algorithms for the Prize-Collecting k-Steiner Tree Problem},
year = {2022},
journal = {Tsinghua Science and Technology},
volume = {27},
number = {5},
pages = {785-792},
keywords = {approximation algorithm, prize-collecting, Steiner tree},
url = {https://www.sciopen.com/article/10.26599/TST.2021.9010053},
doi = {10.26599/TST.2021.9010053},
abstract = {In this paper, we study the prize-collecting  k-Steiner tree (PC kST) problem. We are given a graph  G=(V,E) and an integer  k. The graph is connected and undirected. A vertex  r∈V called root and a subset  R⊆V called terminals are also given. A feasible solution for the PC kST 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 PC kST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the  k-Steiner tree ( kST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to  5.}
}