收录:
摘要:
In this paper, we consider the generalized prize-collecting Steiner forest problem, extending the prize-collecting Steiner forest problem. In this problem, we are given a connected graph G= (V, E) and a set of vertex sets V= { V1, V2, , Vl}. Every edge in E has a nonnegative cost, and every vertex set in V has a nonnegative penalty cost. For a given edge set F⊆ E, vertex set Vi∈ V is said to be connected by edge set F if Vi is in a connected component of the F-spanned subgraph. The objective is to find such an edge set F such that the total edge cost in F and the penalty cost of the vertex sets not connected by F is minimized. Our main contribution is to give a 3-approximation algorithm for this problem via the primal-dual method. © 2017, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
Journal of the Operations Research Society of China
ISSN: 2194-668X
年份: 2017
期: 2
卷: 5
页码: 219-231
归属院系: