LP Relaxation and Tree Packing for Minimum k-cuts
LP Relaxation and Tree Packing for Minimum k-cuts
复制标题
最小 k 割的 LP 松弛和树包装
DOI：
10.4230/oasics.sosa.2019.7
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Chao Xu
中科院分区：
文献类型：
--
作者：
C. Chekuri;Kent Quanrud;Chao Xu
Karger使用跨越的树包装来得出用于全局最小切割问题的接近线性时间随机算法，以及大约最小切割的数量。这与他众所周知的随机收缩算法不同。 Thorup通过贪婪的递归树包装开发了针对最低$ k $ cut问题的快速确定性算法。
在本文中，我们重新审视了Naor和Rabani提出的$ K $ cut的LP放松的特性，并由Chekuri，Guha和Naor进行了分析。我们表明，LP的双重双重构成了树木的包装，当与LP的整体差距上的上限结合在一起时，很容易透明地将Karger的Mincut分析扩展到$ K $ - 切割问题。除了算法的简单性及其分析外，这还使我们能够将Thorup算法的运行时间提高到$ n $。我们还提高了$ \ alpha $ - approximate $ k $ cuts的数量。其次，我们简单地证明了LP的完整性差距为$ 2（1-1/N）$。第三，我们表明，对于所有$ k $的所有值，对LP松弛的最佳解决方案完全由输入图的分区的主序列确定。这使我们能够将LP放松与Barahona和Ravi和Sinha的拉格朗日放松方法联系起来。它还表明，Thorup考虑的理想递归树包装为LP提供了最佳的双重解决方案。这项工作源于理解和简化Thorup的结果。
Karger used spanning tree packings to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts. This is a different approach from his well-known random contraction algorithm. Thorup developed a fast deterministic algorithm for the minimum $k$-cut problem via greedy recursive tree packings.
In this paper we revisit properties of an LP relaxation for $k$-cut proposed by Naor and Rabani, and analyzed by Chekuri, Guha and Naor. We show that the dual of the LP yields a tree packing, that when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Karger's analysis for mincut to the $k$-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorup's algorithm by a factor of $n$. We also improve the bound on the number of $\alpha$-approximate $k$-cuts. Second, we give a simple proof that the integrality gap of the LP is $2(1-1/n)$. Third, we show that an optimum solution to the LP relaxation, for all values of $k$, is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangian relaxation approach of Barahona and Ravi and Sinha; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP. This work arose from an effort to understand and simplify the results of Thorup.
DOI：
10.1145/3055399.3055412
发表时间：
2016-11
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Pasin Manurangsi
通讯作者：
Pasin Manurangsi