New Approximation Algorithms for the Steiner Tree Problems

被引：0
|
作者：
Marek Karpinski
Alexander Zelikovsky
机构：
[1] University of Bonn,Department of Computer Science
[2] International Computer Science Institute,Department of Computer Science, Thornton Hall
[3] University of Virginia,undefined
来源：
Journal of Combinatorial Optimization | 1997年 / 1卷
关键词：
Mathematical Modeling; Approximation Algorithm; Industrial Mathematic; Discrete Geometry; Approximation Ratio;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：18
相关论文
共 50 条
  • [1] New approximation algorithms for the Steiner tree problems
    Karpinski, M
    Zelikovsky, A
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 1997, 1 (01) : 47 - 65
  • [2] Approximation Algorithms for Priority Steiner Tree Problems
    Sahneh, Faryad Darabi
    Kobourov, Stephen
    Spence, Richard
    COMPUTING AND COMBINATORICS (COCOON 2021), 2021, 13025 : 112 - 123
  • [3] Approximation Algorithms for Steiner Tree Augmentation Problems
    Ravi, R.
    Zhang, Weizhong
    Zlatin, Michael
    PROCEEDINGS OF THE 2023 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2023, : 2429 - 2448
  • [4] Elementary approximation algorithms for prize collecting Steiner tree problems
    Gutner, Shai
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, PROCEEDINGS, 2008, 5165 : 246 - 254
  • [5] Elementary approximation algorithms for prize collecting Steiner tree problems
    Gutner, Shai
    INFORMATION PROCESSING LETTERS, 2008, 107 (01) : 39 - 44
  • [6] Approximation algorithms for constrained node weighted steiner tree problems
    Moss, A.
    Rabani, Y.
    SIAM JOURNAL ON COMPUTING, 2007, 37 (02) : 460 - 481
  • [7] Approximation algorithms for directed Steiner problems
    Charikar, M
    Chekuri, C
    Cheung, TY
    Dai, Z
    Goel, A
    Guha, S
    Li, M
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 33 (01): : 73 - 91
  • [8] APPROXIMATION ALGORITHMS FOR THE TERMINAL STEINER TREE PROBLEM
    Chen, Yen Hung
    Lin, Ying Chin
    APPLIED AND COMPUTATIONAL MATHEMATICS, 2018, 17 (03) : 246 - 255
  • [9] On approximation algorithms for the terminal Steiner tree problem
    Drake, DE
    Hougardy, S
    INFORMATION PROCESSING LETTERS, 2004, 89 (01) : 15 - 18
  • [10] New primal-dual algorithms for Steiner tree problems
    Melkonian, Vardges
    COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (07) : 2147 - 2167
12345