Worst-case performance of Rayward-Smith's Steiner tree heuristic
type: Item
instance of: scholarly article
title: Worst-case performance of Rayward-Smith's Steiner tree heuristic
zbMATH Open document ID: 0662.68039
DOI: 10.1016/0020-0190(88)90225-6
author: Bernard M. Waxman
author: Makoto Imase
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
full work available at URL: https://openscholarship.wustl.edu/cgi/viewcontent.cgi
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 4082970
zbMATH Keywords: NP-complete
zbMATH Keywords: worst-case
zbMATH Keywords: Steiner tree
zbMATH Keywords: approximation algorithm
zbMATH Keywords: optimal
MaRDI profile type: Publication
OpenAlex ID: W2087598714
cites work: Routing to Multiple Destinations in Computer Networks
cites work: Q4142699
cites work: A fast algorithm for Steiner trees
cites work: The computation of nearly minimal Steiner trees in graphs
cites work: On finding steiner vertices
cites work: Q3874241
cites work: Steiner problem in networks: A survey
description: scientific article; zbMATH DE number 4082970