Worst-case performance of Rayward-Smith's Steiner tree heuristic (Q1114397)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Worst-case performance of Rayward-Smith's Steiner tree heuristic |
scientific article |
Statements
Worst-case performance of Rayward-Smith's Steiner tree heuristic (English)
0 references
1988
0 references
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.
0 references
NP-complete
0 references
worst-case
0 references
Steiner tree
0 references
approximation algorithm
0 references
optimal
0 references
