A NEARLY BEST-POSSIBLE APPROXIMATION ALGORITHM FOR NODE-WEIGHTED STEINER TREES
A NEARLY BEST-POSSIBLE APPROXIMATION ALGORITHM FOR NODE-WEIGHTED STEINER TREES
复制标题
DOI：
10.1006/jagm.1995.1029
复制
发表时间：
1995-07-01
影响因子：
--
通讯作者：
RAVI, R
中科院分区：
文献类型：
--
作者：
KLEIN, P;RAVI, R
给出了节点加权Steiner树问题的一次近似算法。其性能保证在最佳可能的恒定因子内，除非（$）超过或等于NP的bar P超集。（（$）over bar P代表复杂度类确定性准多项式时间，或DTIME[n（polylog）（n）]。我们的算法推广到处理其他网络设计问题。(C)出版社：Academic Press
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.