{Reference Type}: Journal Article
{Title}: Algorithms for the Prize-Collecting k-Steiner Tree Problem
{Author}: Han, Lu; Wang, Changjun; Xu, Dachuan; Dongmei, Zhang
{Journal}: Tsinghua Science and Technology
{ISBN/ISSN}: 1007-0214
{Year}: 2022
{Volume}: 27
{Issue}: 5
{Pages}: 785-792
{DOI}: 10.26599/TST.2021.9010053
{Keywords}: approximation algorithm
{Keywords}: prize-collecting
{Keywords}: Steiner tree
{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.
{URL}: https://www.sciopen.com/article/10.26599/TST.2021.9010053
{Language}: en