In this paper,we study the prize-collecting k-Steiner tree(PCkST)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 PCkST 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 PCkST.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.

Lu Han;Changjun Wang;Dachuan Xu;Dongmei Zhang

School of Science,Beijing University of Posts and Telecommunications,Beijing 100876,China;Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China;Beijing Institute for Scientific and Engineering Computing,Beijing University of Technology,Beijing 100124,China;School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250101,China

清华大学学报自然科学版（英文版）

[1]Lu Han;Changjun Wang;Dachuan Xu;Dongmei Zhang-.Algorithms for the Prize-Collecting k-Steiner Tree Problem)[J].清华大学学报自然科学版（英文版）,2022(05):785-792

PCkST,PCST,kST

Algorithms,Prize,Collecting,Steiner,Tree,Problem,In,this,paper,we,study,prize,collecting,tree,problem,We,are,given,graph,integer,connected,undirected,vertex,called,subset,terminals,also,feasible,solution,rooted,connecting,least,vertices,Excluding,from,incurs,penalty,including,wish,find,minimum,total,sum,costs,edges,not,present,simple,approximation,ratio,This,uses,algorithms,subroutines,Then,propose,primal,dual,improve

0.448259