ECCC - TR08-094

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR08-094 | 10th October 2008 00:00

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two

Contact

Add Comment

TR08-094 Authors: Piotr Berman, Marek Karpinski, Alexander Zelikovsky
Publication: 10th October 2008 15:20
Downloads: 3050

Keywords:

Approximation Algorithms, Approximation Factors, Greedy Heuristics, Metric Spaces, Steiner Tree Problem

Abstract:

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.

ISSN 1433-8092 | Imprint