考虑一个加权图g=（v，e，w）。我们给出了一个顶点Vúi的子集族。
steiner森林是一个森林，对于每个顶点子集，v_i都用一棵树连接该子集中的所有顶点。
示例：只有一个子集V_1=V。在本例中，Steiner林是整个图的生成树。
示例：一个图p4（有4个顶点的路径）和两个子集：v1={v1，v4}和v2={v2，v3}。本例中的steiner树是整个图。
够理论了。找到这样一个最小重量的森林是困难的（np完全）。你知道用更快的近似算法找到这样一个具有非最佳权重的森林吗？
最佳答案
Vijay Vazirani的近似算法的第20章描述了一个生成Steiner森林的模式。分析使用了lp对偶，他用它来确定算法的因子：
（这是一个factor-2算法，但在实践中它可能运行得很好）
Approximation Algorithms
另外：请参阅22.5中的注释，其中描述了三篇论文供进一步阅读，包括对该主题的调查。