Tsinghua Science and Technology 2022, 27(5): 785-792
Published: 17 March 2022
In this paper, we study the prize-collecting -Steiner tree (PC ST) problem. We are given a graph and an integer . The graph is connected and undirected. A vertex called root and a subset called terminals are also given. A feasible solution for the PC ST is a tree rooted at and connecting at least vertices in . 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 is the sum of the edge costs of the edges in and the penalty costs of the vertices not in . We present a simple approximation algorithm with the ratio of for the PC ST. This algorithm uses the approximation algorithms for the prize-collecting Steiner tree (PCST) problem and the -Steiner tree ( ST) problem as subroutines. Then we propose a primal-dual based approximation algorithm and improve the approximation ratio to .