Document Type
Technical Report
Publication Date
1988-01-01
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.
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
COinS
Comments
Permanent URL: http://dx.doi.org/10.7936/K7V986CJ