摘要
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_(1),V_(2),…,V_(l)}.Assume c:E→R_(+)is an edge cost function andπ:2^(V)→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.
基金
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)
Overseas Expertise Introduction Program of Hebei Auspices(No.25305008).