most recent 30 from http://mathoverflow.net 2013-05-19T02:09:15Z http://mathoverflow.net/feeds/question/21859 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph Tadeusz A. Kadłubowski 2010-04-19T17:17:01Z 2010-04-19T17:50:43Z

<p>Hello.</p> <h2>Background</h2> <p>Consider a weighted graph $G=(V,E,w)$. We are given a family of $k$ disjoint subsets of vertices $V_1, \cdots, V_k$.</p> <p>A Steiner Forest is a forest that for each subset of vertices $V_i$ connects all of the vertices in this subset with a tree.</p> <p>Example: only one subset of vertices $V_1 = V$. In this case a Steiner forest is a spanning tree of the whole graph.</p> <h2>Question</h2> <blockquote> <p>Finding such a forest with minimal weight is difficult (NP-complete). Do you know any quicker approximate algorithm to find such a forest with non-optimal weight?</p> </blockquote>

http://mathoverflow.net/questions/21859/an-approximate-algorithm-for-finding-steiner-forest-in-a-graph/21865#21865 Hsien-Chih Chang 2010-04-19T17:50:43Z 2010-04-19T17:50:43Z

<p>There is a 2-approximation algorithm, see e.g. </p> <blockquote> <p>A General Approximation Technique For Constrained Forest Problems, Michel Goemans, David P. Williamson, SIAM Journal on Computing 1992.</p> </blockquote> <p>For special kind of graphs, better bounds can be obtained: for planar graphs there is a PTAS,</p> <blockquote> <p>Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dániel Marx, STOC '10.</p> </blockquote>