Worst-case performance of Rayward-Smith's Steiner tree heuristic (Q1114397): Difference between revisions

We prove that the worst-case performance of the Steiner tree approximation algorithm by \textit{V. J. Rayward-Smith} (RS) [Int. J. Math. Educ. Sci. Technol. 14, 15-23 (1983; Zbl 0512.05024)] 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.