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:
“To many men ... the miasma of peace seems more suffocating than the bracing air of war.”
—George Steiner (b. 1929)
“A magazine or a newspaper is a shop. Each is an experiment and represents a new focus, a new ratio between commerce and intellect.”
—John Jay Chapman (1862–1933)