Title

Worst Case Performance of Rayward-Smith's Steiner Tree Heuristic

Authors

Bernard M. Waxman, Washington University in St. Louis
Makoto Imase, NTT Software Laboratories

Document Type

Technical Report

Publication Date

1988-01-01

Filename

WUCS-88-13.pdf

DOI:

10.7936/K7V986CJ

Technical Report Number

WUCS-88-13

Abstract

In this paper, we prove that the worst case performance of the Steiner tree approximation algorithm by Rayward-Smith is within two times optimal and that two is the best bound in the sense that there are instances for which RS will do worse than any value less than two.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7V986CJ

Recommended Citation

Waxman, Bernard M. and Imase, Makoto, "Worst Case Performance of Rayward-Smith's Steiner Tree Heuristic" Report Number: WUCS-88-13 (1988). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/770