An improved algorithm for the Steiner tree problem with bounded edge-length
| Autor: | Chi-Yeh Chen, Sun-Yuan Hsieh |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
General Computer Science
Computer Networks and Communications Heuristic Applied Mathematics Improved algorithm Edge (geometry) Steiner tree problem Theoretical Computer Science Combinatorics symbols.namesake Computational Theory and Mathematics Bounded function symbols MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Journal of Computer and System Sciences. 123:20-36 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2021.07.003 |
| Popis: | This work firstly studies the Steiner tree problem with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of d ln 4 d + ln 4 − 1 + ϵ for general graphs and approximation ratio of 73 ⋅ d 60 ⋅ d + 13 + ϵ for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + ϵ for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect