Journal of the Operations Research Society of China
Special Issue: Discrete optimization
Previous Articles Next Articles
Online:
Published:
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.
Key words: Prize-collecting ·, Steiner forest ·, Approximation algorithm ·, Primal-dual
Lu Han · Da-Chuan Xu · Dong-Lei Du·Chen-Chen Wu. A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem[J]. Journal of the Operations Research Society of China, doi: 10.1007/s40305-017-0164-4.
0 / / Recommend
Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks
URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-017-0164-4
https://www.jorsc.shu.edu.cn/EN/Y2017/V5/I2/219
A Modified and Simplified Full Nesterov–Todd Step O(N) Infeasible Interior-Point Method for Second-Order Cone Optimization