In this paper, we consider the generalized prize-collecting Steiner forest problem with submodular penalties (GPCSF-SP problem). In this problem, we are given an undirected connected graph G=(V, E) and a collection of disjoint vertex subsets V={V1, V2, · · ·, Vl}. Assume c:E → $\mathbb{R}$+ is an edge cost function and π:2V → $\mathbb{R}$+ is a submodular penalty function. The objective of the GPCSF-SP problem is to find an edge subset F such that the total cost including the edge cost in F and the penalty cost of the subcollection S containing these Vi not connected by F is minimized. By using the primal-dual technique, we give a 3-approximation algorithm for this problem.
Xiao-Dan Jia, Bo Hou, Wen Liu
. An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties[J]. Journal of the Operations Research Society of China, 2022
, 10(1)
: 183
-192
.
DOI: 10.1007/s40305-021-00355-8
[1] Archer, A., Bateni, M.H., Hajiaghayi, M.T.:Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40(2), 309-332(2011)
[2] Bienstock, D., Goemans, M.X., Simchi-Levi, D.:A note on the prize collecting traveling salesman problem. Math. Program. 59(1), 413-420(1993)
[3] Han, L., Xu, D.C., Du, D.L., Wu, C.C.:A primal-dual algorithm for the generalized prize-collecting Steiner forest problem. J. Oper. Res. Soc. China 5(2), 219-231(2017)
[4] Hajiaghayi, M.T., Jain, K.:The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In:Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, Society for Industrial and Applied Mathematics, pp. 631-640(2006)
[5] Kortsarz, G., Nutov, Z.:Approximating minimum cost connectivity problems. In:Gonzales, T. (ed.) Handbook of Approximation Algorithms and Metaheuristics. CRC Press, Boca Raton (2007)
[6] Sharma, Y., Swamy, C., Williamson, D.P.:Approximation algorithms for prize collecting forest problems with submodular penalty functions. In:Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, pp. 1275-1284(2007)
[7] Agrawal, A., Klein, P.N., Ravi, R.:When trees collide:an approximation algorithm for the generalized Steiner problem on networks. In:Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 134-144(1991)
[8] Goemans, M.X., Williamson, D.P.:A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296-317(1995)
[9] Byrka, J., Grandoni, F., Rothvoss, T.:Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 1-33(2013)
[10] Fleischer, L., Iwata, S.:A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl. Math. 131, 311-322(2003)
