论文标题
递归随机收缩重新审视
Recursive Random Contraction Revisited
论文作者
论文摘要
在本说明中，我们重新访问了Karger和Stein的递归随机收缩算法，以查找图中的最小切割。我们的重新访问是由Fox，Panigrahi和Zhang的论文引起的，该论文将Karger-Stein算法扩展到最低限度和最低$ K $ - $ k $ - 超图。当专门研究图的情况时，该算法与原始的Karger-Stein算法有所不同。我们表明，在这种情况下，分析变得特别干净：我们可以证明，该算法返回$ n $ node图中的固定最小切割的可能性在下面以$ 1/（2H_N_N-2）$限制，其中$ h_n $是$ n $ n $ n $ th谐波数。我们还考虑了该算法的其他类似变体，并表明没有这种算法可以实现渐近地找到固定最小切割的概率。
In this note, we revisit the recursive random contraction algorithm of Karger and Stein for finding a minimum cut in a graph. Our revisit is occasioned by a paper of Fox, Panigrahi, and Zhang which gives an extension of the Karger-Stein algorithm to minimum cuts and minimum $k$-cuts in hypergraphs. When specialized to the case of graphs, the algorithm is somewhat different than the original Karger-Stein algorithm. We show that the analysis becomes particularly clean in this case: we can prove that the probability that a fixed minimum cut in an $n$ node graph is returned by the algorithm is bounded below by $1/(2H_n-2)$, where $H_n$ is the $n$th harmonic number. We also consider other similar variants of the algorithm, and show that no such algorithm can achieve an asymptotically better probability of finding a fixed minimum cut.
