A 4-Approximation Algorithm for k-Prize Collecting Steiner Tree Problems

Yusa Matsuda, Satoshi Takahashi

This paper studies a 4-approximation algorithm for k-prize collecting Steiner tree problems. This problem generalizes both k-minimum spanning tree problems and prize collecting Ste…