Primal-dual approximation algorithms for the Prize-Collecting Steiner Tree Problem
The primal-dual scheme has been used to provide approximation algorithms for many problems. Goemans and Williamson gave a (2 - 1 / (n - 1))-approximation for the Prize-Collecting Steiner Tree Problem that runs in O(n(3) log n) time-it applies the primaldual scheme once for each of the n vertices of the graph. We present a primal-dual algorithm that runs in O(n(2) log n), as it applies this scheme only once, and achieves the slightly better ratio of (2 - 2/n). We also show a tight example for the analysis of the algorithm and discuss briefly a couple of other algorithms described in the literature. (c) 2007 Elsevier B.V. All rights reserved.
approximation algorithms prize-collecting steiner tree primal-dual method