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

• • 上一篇

收稿日期:2020-07-30 修回日期:2020-12-08 出版日期:2022-03-30 发布日期:2022-03-23
基金资助:
This work is supported by the National Natural Science Foundation of China (No. 11971146), the Natural Science Foundation of Hebei Province (Nos. A2019205089 and A2019205092), Hebei Province Foundation for Returnees (No. CL201714) and Overseas Expertise Introduction Program of Hebei Auspices (No. 25305008).

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

中图分类号:

90C27

. [J]. Journal of the Operations Research Society of China, 2022, 10(1): 183-192.

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.

参考文献

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

相关文章 15

[1]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 129-148.
[2]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 149-161.
[3]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 162-178.
[4]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 309-324.
[5]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 325-343.
[6]	. [J]. Journal of the Operations Research Society of China, 2025, 13(4): 919-945.
[7]	. [J]. Journal of the Operations Research Society of China, 2025, 13(4): 1083-1107.
[8]	. [J]. Journal of the Operations Research Society of China, 2025, 13(4): 1157-1180.
[9]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 535-554.
[10]	. [J]. Journal of the Operations Research Society of China, 2025, 13(1): 142-160.
[11]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 996-1021.
[12]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 627-648.
[13]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 729-755.
[14]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 757-771.
[15]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 795-807.

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价