New Approximation Algorithms for the Steiner Tree Problems

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. Dept. of Computer Science, University of Bonn, 53117 Bonn. Research partially supported by the Leibniz Center for Research in Computer Science, by the DFG Grant KA 67314-1, by the ESPRIT BR Grants 7097 and by ECUS030. Email: marek@cs.uni-bonn.de. y Institute of Mathematics, Akademiei 5, Kishinev, 277028, Moldova. Research partially supported by Volkswagen Stiftung. Parts of this work were done in Max-Planck-Institut fur Informatik, Saarbrucken. Email: 17azz@mathem.moldova.su. 1 Introduction We consider a metric space with a distance function d. For any set of ..