Approximation algorithms for prize collecting forest problems with submodular penalty functions
Yogeshwer Sharma, Chaitanya Swamy, David P. Williamson · Symposium on Discrete Algorithms · 2007
In this paper, we study the prize-collecting version of constrained forest problems with an arbitrary 0-1 connectivity requirement function and a submodular penalty function. Our framework generalizes the Prize Collecting Generalized Steiner Tree framework of Hajiaghayi and Jain [HJ06] to incorporate more general connectivity requirements and penalty functions. We generalize their primal-dual algorithm using submodular function minimization to give a 3-approximation algorithm, and devise an LP rounding algorithm with a performance guarantee of 2.54.