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:
“The variables are surprisingly few.... One can whip or be whipped; one can eat excrement or quaff urine; mouth and private part can be meet in this or that commerce. After which there is the gray of morning and the sour knowledge that things have remained fairly generally the same since man first met goat and woman.”
—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)