A NEARLY BEST-POSSIBLE APPROXIMATION ALGORITHM FOR NODE-WEIGHTED STEINER TREES

被引：251

作者：

KLEIN, P ^{[1
]}

RAVI, R ^{[1
]}

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

来源：

JOURNAL OF ALGORITHMS | 1995年 / 19卷 / 01期

关键词：

D O I：

10.1006/jagm.1995.1029

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We give the first approximation algorithm for the node-weighted Steiner tree problem. Its performance guarantee is within a constant factor of the best possible unless ($) over bar P superset of or equal to NP. (($) over bar P stands for the complexity class deterministic quasi-polynomial time, or DTIME[n(polylog) (n)].) Our algorithm generalizes to handle other network-design problems. (C) 1995 Academic Press, Inc.

引用

页码：104 / 115

页数：12

共 25 条

[1] AGRAWAL A, 1991, 23RD P ANN ACM S THE, P134
[2] [Anonymous], 1980, MATH JAPONICA
[3] BERMAN P, 1991, COMMUNICATION
[4] Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233
[5] DREYFUS SE, 1971, NETWORKS, V1, P195
[6] Edmonds J, 1973, MATHEMATICAL PROGRAM, V5, P88
[7] GEOMANS MX, 1992, 3RD P ANN ACM SIAM S, P307
[8] Hakimi S. L., 1971, Networks, V1, P113, DOI 10.1002/net.3230010203
[9] STEINER TREE PROBLEMS
HWANG, FK
RICHARDS, DS
[J]. NETWORKS, 1992, 22 (01) : 55 - 89
[10] APPROXIMATION ALGORITHMS FOR COMBINATORIAL PROBLEMS
JOHNSON, DS
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) : 256 - 278

← 1 2 3 →