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)
“Personal rights, universally the same, demand a government framed on the ratio of the census: property demands a government framed on the ratio of owners and of owning.”
—Ralph Waldo Emerson (1803–1882)