A minimum spanning tree is a feasible but not usually optimal solution to the Steiner tree problem. The Steiner ratio is the largest possible ratio between the total length of a minimum spanning tree and the total length of a minimum Steiner tree.
In the metric Steiner tree problems, the Steiner ratio is 2. Therefore an algorithm that finds a minimum spanning tree is a polynomial-time factor-2 approximation algorithm for the metric Steiner tree problem.
In the Euclidean Steiner tree problem, the Steiner ratio is conjectured to be . Despite earlier claims of a proof, the conjecture is still open.
Read more about this topic: Steiner Tree Problem
Famous quotes containing the words steiner and/or ratio:
“Language can only deal meaningfully with a special, restricted segment of reality. The rest, and it is presumably the much larger part, is silence.”
—George Steiner (b. 1929)
“Official dignity tends to increase in inverse ratio to the importance of the country in which the office is held.”
—Aldous Huxley (1894–1963)