New Approximation Algorithms for the Steiner Tree Problems |
| |
| Authors: | Marek Karpinski Alexander Zelikovsky |
| |
| Affiliation: | (1) Department of Computer Science, University of Bonn, 53117 Bonn, and;(2) International Computer Science Institute, Berkeley, California, Email;(3) Department of Computer Science, Thornton Hall, University of Virginia, VA, 22903-2442, Email |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
