A 1.598 approximation algorithm for the Steiner problem in graphs

被引：0

作者：

Hougardy, S ^{[1
]}

Prömel, HJ ^{[1
]}

机构：

[1] Humboldt Univ, Inst Informat, D-10099 Berlin, Germany

来源：

PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS | 1999年

关键词：

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a general iterative framework for improving the performance ratio of Steiner tree approximation algorithms. By applying this framework to one specific algorithm we obtain a new polynomial time approximation algorithm for the Steiner tree problem in graphs that achieves a performance ratio of 1.598 after II iterations. This beats the so far best known factor of 1.644 due to Karpinski and Zelikovsky [10]. With the help of a computer program we estimate the limit performance of our algorithm to be 1.588.

引用

页码：448 / 453

页数：6

共 50 条

[31] An approximation algorithm for the k-generalized Steiner forest problem [J].

Jiawen Gao ;

Suogang Gao ;

Wen Liu ;

Weili Wu ;

Ding-Zhu Du ;

Bo Hou .

Optimization Letters, 2021, 15 :1475-1483

[32] FasterDSP: A faster approximation algorithm for directed Steiner tree problem [J].

Hsieh, Ming-I ;

Wu, Eric Hsiao-Kuang ;

Tsai, Meng-Feng .

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2006, 22 (06) :1409-1425

[33] A factor 2 approximation algorithm for the generalized Steiner network problem [J].

Jain, K .

COMBINATORICA, 2001, 21 (01) :39-60

[34] An approximation algorithm for the k-generalized Steiner forest problem [J].

Gao, Jiawen ;

Gao, Suogang ;

Liu, Wen ;

Wu, Weili ;

Du, Ding-Zhu ;

Hou, Bo .

OPTIMIZATION LETTERS, 2021, 15 (04) :1475-1483

[35] A factor 2 approximation algorithm for the generalized Steiner network problem [J].

Jain, K .

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :448-457

[36] Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane [J].

Li, ZM ;

Zhu, DM ;

Ma, SH .

JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY, 2004, 19 (06) :791-794

[37] AN 11-6-APPROXIMATION ALGORITHM FOR THE NETWORK STEINER PROBLEM [J].

ZELIKOVSKY, AZ .

ALGORITHMICA, 1993, 9 (05) :463-470

[38] A PRIMAL-DUAL APPROXIMATION ALGORITHM FOR THE STEINER FOREST PROBLEM [J].

RAVI, R .

INFORMATION PROCESSING LETTERS, 1994, 50 (04) :185-190

[39] Approximation algorithm for bottleneck Steiner tree problem in the Euclidean plane [J].

Zi-Mao Li ;

Da-Ming Zhu ;

Shao-Han Ma .

Journal of Computer Science and Technology, 2004, 19 :791-794

[40] Improved Steiner tree approximation in graphs [J].

Robins, G ;

Zelikovsky, A .

PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2000, :770-779

← 1 2 3 4 5 →