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:
“It is not the literal past that rules us, save, possibly, in a biological sense. It is images of the past.... Each new historical era mirrors itself in the picture and active mythology of its past or of a past borrowed from other cultures. It tests its sense of identity, of regress or new achievement against that past.”
—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)