Editing Steiner tree problem (section)

==Approximating the Steiner tree==

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices, as first published in 1981 by Kou et al.{{sfnp|Kou|Markowsky|Berman|1981}} The metric closure of a graph <math>G</math> is the complete graph in which each edge is weighted by the shortest path distance between the nodes in <math>G</math>. This algorithm produces a tree whose weight is within a <math>2 - 2/t</math> factor of the weight of the optimal Steiner tree where <math>t</math> is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. This approximate solution is computable in <math>O(|S| |V|^2) </math> [[Time complexity#Polynomial time|polynomial time]] by first solving the [[Shortest path problem#All-pairs shortest paths|all-pairs shortest paths problem]] to compute the metric closure, then by solving the [[minimum spanning tree|minimum spanning tree problem]].

Another popular algorithm to approximate the Steiner tree in graphs was published by Takahashi and Matsuyama in 1980.{{sfnp|Takahashi|Matsuyama|1980}} Their solution incrementally builds up the Steiner tree by starting from an arbitrary vertex, and repeatedly adding the shortest path from the tree to the nearest vertex in <math>S</math> that has not yet been added. This algorithm also has <math> O(|S| |V|^2)</math> running time, and produces a tree whose weight is within <math>2 - 2/|S|</math> of optimal.

In 1986, Wu et al.{{sfnp|Wu|Widmayer|Wong|1986}} improved dramatically on the running time by avoiding precomputation of the all-pairs shortest paths. Instead, they take a similar approach to [[Kruskal's algorithm]] for computing a minimum spanning tree, by starting from a forest of <math>|S|</math> disjoint trees, and "growing" them simultaneously using a breadth-first search resembling [[Dijkstra's algorithm]] but starting from multiple initial vertices. When the search encounters a vertex that does not belong to the current tree, the two trees are merged into one. This process is repeated until only one tree remains. By using a [[Heap (data structure)]] to implement the priority queue and a [[disjoint-set data structure]] to track to which tree each visited vertex belongs, this algorithm achieves <math>O(|E| \log |V|)</math> running time, although it does not improve on the <math>2 - 2/t</math> cost ratio from Kou et al.

A series of papers provided approximation algorithms for the minimum Steiner tree problem with approximation ratios that improved upon the <math>2 - 2/t</math> ratio. This sequence culminated with Robins and Zelikovsky's algorithm in 2000 which improved the ratio to 1.55 by iteratively improving upon the minimum cost terminal spanning tree. More recently, however, Byrka et al. proved an <math>\ln(4) + \varepsilon \le 1.39</math> approximation using a linear programming relaxation and a technique called iterative, randomized rounding.{{sfnp|Byrka|Grandoni|Rothvoß|Sanita|2010}}