A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem

DOI10.1007/BF01784988zbMath0707.90082OpenAlexW2021624778MaRDI QIDQ920030

Cid Carvalho De Souza, Celso Carneiro Ribeiro

Publication date: 1990

Published in: OR Spektrum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01784988

zbMATH Keywords

heuristicsminimum rectilinear Steiner tree problemtight worst case upper bound

Mathematics Subject Classification ID

Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Discrete location and assignment (90B80) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (1)

Heuristics for the minimum rectilinear Steiner tree problem: New algorithms and a computational study

Cites Work

• On Steiner Minimal Trees with Rectilinear Distance
• Use of Steiner's problem in suboptimal routing in rectilinear metric
• An O(n log n) algorithm for suboptimal rectilinear Steiner trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete

This page was built for publication: A tight worst case bound for the performance ratio of heuristics for the minimum rectilinear Steiner tree problem