New approximation algorithms for the Steiner tree problems

被引：125

作者：

Karpinski, M ^{[1
]}

Zelikovsky, A

机构：

[1] Univ Bonn, Dept Comp Sci, D-53117 Bonn, Germany

[2] Int Comp Sci Inst, Berkeley, CA 94704 USA

[3] Univ Virginia, Dept Comp Sci, Charlottesville, VA 22903 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 1997年 / 1卷 / 01期

关键词：

Mathematical Modeling; Approximation Algorithm; Industrial Mathematic; Discrete Geometry; Approximation Ratio;

D O I：

10.1023/A:1009758919736

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel technique of choosing Steiner points in dependence on the possible deviation from the optimal solutions. We achieve the best up to now approximation ratios of 1.644 in arbitrary metric and 1.267 in rectilinear plane, respectively.

引用

页码：47 / 65

页数：19

共 23 条

[1]

[Anonymous], 1980, Math Japonica

[2] IMPROVED APPROXIMATIONS FOR THE STEINER TREE PROBLEM [J].

BERMAN, P ;

RAMAIYER, V .

JOURNAL OF ALGORITHMS, 1994, 17 (03) :381-408

[3]

BERMAN P, 1991, CS9105 PENNS STAT U

[4]

BERMAN P, 1994, LECT NOTES COMPUTER, V855, P60

[5] THE STEINER PROBLEM WITH EDGE LENGTH-1 AND LENGTH-2 [J].

BERN, M ;

PLASSMANN, P .

INFORMATION PROCESSING LETTERS, 1989, 32 (04) :171-176

[6]

BERN M, 1995, IN PRESS PWS PUBLICA

[7]

Borchers A., 1995, Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, P641, DOI 10.1145/225058.225282

[8]

DU DZ, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P431, DOI 10.1109/SFCS.1991.185402

[9]

Fossmeier U., 1993, LNCS, V762, P533

[10] RECTILINEAR STEINER TREE PROBLEM IS NP-COMPLETE [J].

GAREY, MR ;

JOHNSON, DS .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1977, 32 (04) :826-834

← 1 2 3 →