Matroids and integrality gaps for hypergraphic steiner tree relaxations
Matroids and integrality gaps for hypergraphic steiner tree relaxations
复制标题
超图斯坦纳树松弛的拟阵和完整性差距
DOI：
10.1145/2213977.2214081
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
R. Zenklusen
中科院分区：
文献类型：
--
作者：
M. Goemans;Neil Olver;T. Rothvoss;R. Zenklusen
直到最近，Lp松弛在Steiner树问题的近似算法设计中只起到了非常有限的作用。特别地，在Byrka等人之前，没有(有效可解的)Steiner树松弛具有从2有界的完整性间隙。文[3]给出了超图Lp松弛的上界~1.55，并在此基础上给出了ln(4)+ε~1.39近似。有趣的是，即使他们的方法是基于Lp的，他们也不会将产生的解与Lp值进行比较。我们重新审视Steiner树问题的超图LP松弛-一个大量使用拟阵和子模函数理论的方法和结果的问题-它导致更强的完整性缺口、更快的算法和各种独立感兴趣的结构洞察。更确切地说，沿着Byrka等人的算法[3]，我们提出了一个确定性的ln(4)+ε近似，它与Lp值相比较，从而证明了超图松弛的积分间隙的匹配的ln(4)上界。
类似于[3]，我们迭代地修复一个组件并更新LP解。然而，在文[3]中，在收缩组件之后的每一次迭代中，LP都被求解，我们展示了如何通过对精心选择的拟阵的贪婪过程来保持可行性。除了避免在每次迭代中求解超图LP的昂贵步骤外，我们的算法还可以使用简单的势函数来分析。当考虑受限图拓扑时，这个势函数提供了一种简单的方法来确定更强的逼近保证和完整性间隙。特别地，这很容易导致拟二部图的超图松弛的整度间隙的上界为73/60~1.217。
此外，对于拟二部图的情形，我们给出了一个简单的算法，将双向割松弛的最优解转化为超图松弛的最优解，从而得到了拟二部图的73/60的快速逼近。此外，我们展示了如何通过计算最大流来解决超图松弛的分离问题，这提供了一种方法来获得我们所使用的拟阵的快速独立预言。
Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. In particular, no (efficiently solvable) Steiner tree relaxation was known to have an integrality gap bounded away from 2, before Byrka et al. [3] showed an upper bound of ~1.55 of a hypergraphic LP relaxation and presented a ln(4)+ε ~1.39 approximation based on this relaxation. Interestingly, even though their approach is LP based, they do not compare the solution produced against the LP value. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem---one that heavily exploits methods and results from the theory of matroids and submodular functions---which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, along the lines of the algorithm of Byrka et al.[3], we present a deterministic ln(4)+ε approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap of hypergraphic relaxations.
Similarly to [3], we iteratively fix one component and update the LP solution. However, whereas in [3] the LP is solved at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This potential function gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 ~1.217 upper bound on the integrality gap of hypergraphic relaxations for quasi-bipartite graphs.
Additionally, for the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, which provides a way to obtain a fast independence oracle for the matroids that we use in our approach.