Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-030 | 20th June 1995 00:00

New Approximation Algorithms for the Steiner Tree Problems

RSS-Feed

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.



ISSN 1433-8092 | Imprint