Steiner Tree Problem - Steiner Ratio

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 shoot a man because one disagrees with his interpretation of Darwin or Hegel is a sinister tribute to the supremacy of ideas in human affairs—but a tribute nevertheless.
    —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)