New Approximation Algorithms for the Steiner Tree Problems
| Title | New Approximation Algorithms for the Steiner Tree Problems |
| Publication Type | Technical Report |
| Year of Publication | 1995 |
| Authors | Karpinski, M., & Zelikovsky A. |
| Other Numbers | 976 |
| Keywords | Approximation Algorithms, Approximation Ratio, Network Steiner Tree Problem, Rectilinear Steiner Tree Problem |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-036.pdf |
| Bibliographic Notes | ICSI Technical Report TR-95-036 |
| Abbreviated Authors | M. Karpinski and A. Zelikovsky |
| ICSI Publication Type | Technical Report |