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 条

[21] AN SST-BASED ALGORITHM FOR THE STEINER PROBLEM IN GRAPHS [J].

BEASLEY, JE .

NETWORKS, 1989, 19 (01) :1-16

[22] An exact branch and bound algorithm for the Steiner problem in graphs [J].

Khoury, BN ;

Pardalos, PM .

COMPUTING AND COMBINATORICS, 1995, 959 :582-590

[23] A high performance approximate algorithm for the Steiner problem in graphs [J].

Guitart, P ;

Basart, JM .

RANDOMIZATION AND APPROXIMATION TECHNIQUES IN COMPUTER SCIENCE, 1998, 1518 :280-293

[24] A polylogarithmic approximation algorithm for the group Steiner tree problem [J].

Garg, N ;

Konjevod, G ;

Ravi, R .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2000, 37 (01) :66-84

[25] ON EFFICIENT IMPLEMENTATION OF AN APPROXIMATION ALGORITHM FOR THE STEINER TREE PROBLEM [J].

KOU, LT .

ACTA INFORMATICA, 1990, 27 (04) :369-380

[26] An approximation algorithm to the k-Steiner Forest problem [J].

Zhang, Peng ;

Xia, Mingji .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (11) :1093-1098

[27] An Improved Approximation Algorithm for the Terminal Steiner Tree Problem [J].

Chen, Yen Hung .

COMPUTATIONAL SCIENCE AND ITS APPLICATIONS - ICCSA 2011, PT III, 2011, 6784 :141-151

[28] An approximation algorithm to the k-steiner forest problem [J].

Zhang, Peng .

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2007, 4484 :728-737

[29] Fully Dynamic Algorithm for the Steiner Tree Problem in Planar Graphs [J].

Raikwar, Hemraj ;

Karmakar, Sushanta .

2022 TENTH INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING WORKSHOPS, CANDARW, 2022, :416-420

[30] A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem [J].

Kamal Jain .

Combinatorica, 2001, 21 :39-60

← 1 2 3 4 5 →