An improved LP-based approximation for steiner tree
An improved LP-based approximation for steiner tree
复制标题
DOI：
10.1145/1806689.1806769
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
J. Byrka;F. Grandoni;T. Rothvoss;Laura Sanità
中科院分区：
文献类型：
--
作者：
J. Byrka;F. Grandoni;T. Rothvoss;Laura Sanità
Steiner树问题是最基本的NP-难问题之一：给定一个加权无向图和一个终端节点子集，找到一个最小成本树。在一系列论文中，这个问题的近似比从2提高到目前最好的1.55 [Robins，Zelikovsky-SIDMA'05]。所有这些算法都是纯组合的。一个长期存在的开放问题是是否存在LP松弛的Steiner树的完整性差距小于2 [Vazirani，Rajagopalan-SODA'99]。本文改进了Steiner树的近似因子，提出了一种基于LP的近似算法。我们的算法是基于一个，看似新颖的，迭代随机舍入技术。我们考虑k-限制Steiner树问题的有向分量割松弛。我们以与最优分数解中相关变量的值成比例的概率对其中一个分量进行采样，并将其收缩。我们将此过程重复适当的次数，最后将采样的分量与剩余图中的最小成本终端生成树一起输出。我们的算法提供了一个解决方案的成本最多ln（4）倍的成本的最佳k-限制Steiner树。这直接意味着Steiner树的ln（4）+ε<1.39近似。作为我们分析的副产品，我们表明，我们的LP的完整性差距最多为1.55 $，因此回答了上述开放性问题。这可能会对一些相关问题产生影响。
The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directed-component cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+ε<1.39 approximation for Steiner tree. As a byproduct of our analysis, we show that the integrality gap of our LP is at most $1.55$, hence answering to the mentioned open question. This might have consequences for a number of related problems.