A 2-approximation for the $k$-prize-collecting Steiner tree problem

Lehilton Lelis Chaves Pedrosa, Hugo Kooki Kasuya Rosado

We consider the $k$-prize-collecting Steiner tree problem. An instance is composed of an integer $k$ and a graph $G$ with costs on edges and penalties on vertices. The objective is…