StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This problem (<a href="http://portal.acm.org/citation.cfm?id=1414423" rel="nofollow noreferrer">Steiner Tree</a>) is NP-hard and max SNP-complete, so there are neither polynomial-time algorithms nor PTAS (arbitrarily close approximations) unless P = NP.</p> <p>The MST can give a weight arbitrarily worse than optimal, unless you know some special feature of your graph (e.g. the graph is planar, or at least that the weights obey the triangle inequality). For example, if you have K_1,000,000,001 with all edge weights 1 and only one target, the optimal solution has weight 1 and the MST has weight 1,000,000,000.</p> <p>If you assume that all edges between targets and all edges between the source and each target exist, you can still overshoot by an arbitrary factor. Consider the above example, but change the edge weight between the target and source to 2,000,000,000,000,000,000 (you're still off by a factor of a billion from optimal).</p> <p>Of course you can transform the graph to 'remove' edge weights that are high in time O(E) or so by traversing the graph. This plus a MST of the set of targets and source gives an approximation ratio of 2.</p> <p>Better approximation ratios exist. Robins & Zelikovsky have a polynomial-time algorithm that is never more than 54.94% worse than optimal: <a href="http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf" rel="nofollow noreferrer">http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf</a></p> <p>Chlebik & Chlebikova show that approximating closer than 1.05% is NP-hard: <a href="http://portal.acm.org/citation.cfm?id=1414423" rel="nofollow noreferrer">The Steiner tree problem on graphs: Inapproximability results</a> (doi 10.1.1.4.1339)</p> <p>If your graph is planar, the situation is better. There's a fast algorithm that gives an arbitrarily-close approximation due to Borradaile, Kenyon-Mathieu & Klein (building on Erickson, Monma, & Veinott): <a href="http://portal.acm.org/citation.cfm?doid=1541885.1541892" rel="nofollow noreferrer">An O(nlogn) approximation scheme for Steiner tree in planar graphs</a> (doi 10.1.1.133.4154)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload