An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties

doi:10.1007/s40305-021-00355-8

Journal of the Operations Research Society of China ›› 2022, Vol. 10 ›› Issue (1): 183-192.doi: 10.1007/s40305-021-00355-8

An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties

Xiao-Dan Jia, Bo Hou, Wen Liu

School of Mathematical Sciences, Hebei Normal University, Shijiazhuang 050024, Hebei, China

Received:2020-07-30 Revised:2020-12-08 Online:2022-03-30 Published:2022-03-23
Contact: Wen Liu, Xiao-Dan Jia, Bo Hou E-mail:liuwen1975@126.com;1755763023@qq.com;houbo1969@163.com

Abstract

Abstract: 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={V₁, V₂, · · ·, V_l}. Assume c:E → $\mathbb{R}$⁺ is an edge cost function and π:2^V → $\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 V_i not connected by F is minimized. By using the primal-dual technique, we give a 3-approximation algorithm for this problem.

Key words: Generalized prize-collecting Steiner forest problem, Submodular function, Primal-dual algorithm

CLC Number:

90C27

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.

TrendMD

References

[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)

An Approximation Algorithm for the Generalized Prize-Collecting Steiner Forest Problem with Submodular Penalties

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Min Li, Dong-Lei Du, Da-Chuan Xu, Zhen-Ning Zhang. A Note on Submodularity Preserved Involving the Rank Functions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 399-407.
[2]	Dong-Lei Du · Yu Li · Nai-Hua Xiu · Da-Chuan Xu. Simultaneous Approximation of Multi-criteria Submodular Function Maximization [J]. Journal of the Operations Research Society of China, 2014, 2(3): 271-290.