On Heuristics for Steiner Minimum Trees

Résumé du livre

Abstract: "Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the smallest ratio of lengths between a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in any metric space with the Steiner ratio less than one, there exists a polynomial-time heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio."