Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
Journal of the Operations Research Society of China
ISSN: 2194-668X
Year: 2017
Issue: 2
Volume: 5
Page: 219-231
Cited Count:
SCOPUS Cited Count: 4
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 5
Affiliated Colleges: