A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem

被引：4

作者：

Han L. ^{[1
]}

Xu D.-C. ^{[1
]}

Du D.-L. ^{[2
]}

Wu C.-C. ^{[3
]}

机构：

[1] Department of Information and Operations Research, Beijing University of Technology, Beijing

[2] Faculty of Business Administration, University of New Brunswick, Fredericton, E3B 5A3, NB

[3] College of Science, Tianjin University of Technology, Tianjin

来源：

Journal of the Operations Research Society of China | 2017年 / 5卷 / 02期

基金：

中国国家自然科学基金; 加拿大自然科学与工程研究理事会;

关键词：

Approximation algorithm; Primal-dual; Prize-collecting; Steiner forest;

D O I：

10.1007/s40305-017-0164-4

中图分类号：

学科分类号：

摘要：

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.

引用

页码：219 / 231

页数：12

共 13 条

[1]

Awerbuch B., Azar Y., Buy-at-bulk network design, Foundations of Computer Science. Proceedings of the 38th Annual Symposium on IEEE, pp. 542-547, (1997)

[2]

Salman F.S., Cheriyan J., Ravi R., Subramanian S., Approximating the single-sink link-installation problem in network design, SIAM J. Optim., 11, pp. 595-610, (2001)

[3]

Bienstock D., Goemans M.X., Simchi-Levi D., Williamson D.P., A note on the prize collecting traveling salesman problem, Math. Program., 59, pp. 413-420, (1993)

[4]

Hajiaghayi M.T., Jain K., The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema, Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, Society for Industrial and Applied Mathematics, pp. 631-640, (2006)

[5]

Gilbert E.N., Pollak H.O., Steiner minimal trees, SIAM J. Appl. Math., 16, pp. 1-29, (1968)

[6]

Karpinski M., Zelikovsky A., New approximation algorithms for the Steiner tree problems, J. Comb. Optim., 1, pp. 47-65, (1997)

[7]

Promel H.J., Steger A., A new approximation algorithm for the Steiner tree problem with performance ratio 5/3, J. Algorithms, 36, pp. 89-101, (2000)

[8]

Robins G., Zelikovsky A., Tighter bounds for graph Steiner tree approximation, SIAM J. Discrete Math., 19, pp. 122-134, (2005)

[9]

Zelikovsky A., An 11/6-approximation algorithm for the network Steiner problem, Algorithmica, 9, pp. 463-470, (1993)

[10]

Byrka J., Grandoni F., Rothvoss T., Sanita L., Steiner tree approximation via iterative randomized rounding, J. ACM, 60, pp. 6:1-6:33, (2013)

← 1 2 →