The Prize-Collecting k-Steiner Tree Problem

摘要

In this paper, we study the prize-collecting fc-Steiner tree problem (PC k-ST), which is an interesting generalization of both the fc-Steiner tree problem (k-ST) and the prize-collecting Steiner tree problem (PCST). In the PC fc-ST. we are given an undirected connected graph G = (V, E), a subset R C V called terminals, a root vertex r ∈ V and an integer A;. Every edge has a non-negative edge cost and every vertex has a non-negative penalty cost. We wish to find an r-rooted tree F that spans at least k vertices in R so as to minimize the total edge costs of F as well as the penalty costs of the vertices not in F. As our main contribution, we propose two approximation algorithms for the PC k-ST with ratios of 5.9672 and 5. The first algorithm is based on an observation of the solutions for the fc-ST and the PCST, and the second one is based on the technique of primal-dual.