论文标题
模拟退火是最小跨越树问题的多项式时间近似方案
Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
论文作者
论文摘要
我们证明，使用适当的冷却时间表模拟退火可以计算任意紧密的恒定因子近似值，以在多项式时间内对最小生成树问题。该结果由Wegener（2005）猜想。更准确地说，用$ n，m，w _ {\ max} $和$ w _ {\ min} $表示MST实例的顶点和边缘的数量以及最大和最小的边缘重量，我们证明，它以初始温度$ t_0 \ ge w _ \ ge w _ {\ ge w _ $ coldere $ coldere $ colders $ cool $ ω（mn \ ln（m））$，概率至少$ 1-1/m $计算时间$ o（\ ell（\ ln \ ln（\ ell）+\ ln（t_0/w _ {\ min}））$ a $ 1+κ$ 1+κ$ 1+κ= \ frac {（1+o（1））\ ln（\ ell m）} {\ ln（\ ell） - \ ln（mn \ ln（m））} $。 Consequently, for any $ε>0$, we can choose $\ell$ in such a way that a $(1+ε)$-approximation is found in time $O((mn\ln(n))^{1+1/ε+o(1)}(\ln\ln n + \ln(T_0/w_{\min})))$ with probability at least $1-1/m$.在所谓的$（1+ε）$ - 分开的权重的特殊情况下，该算法计算一个最佳解决方案（再次在时间$ o（（（mn \ ln（n））^{1+1+1/ε+o（1）}（\ ln \ ln \ ln \ ln n n n n n n+\ ln（t_0/w _））中，这是一个iSN（t_0/w _ {保证$ O（m^{8 + 8/ε}）$。
We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial time. This result was conjectured by Wegener (2005). More precisely, denoting by $n, m, w_{\max}$, and $w_{\min}$ the number of vertices and edges as well as the maximum and minimum edge weight of the MST instance, we prove that simulated annealing with initial temperature $T_0 \ge w_{\max}$ and multiplicative cooling schedule with factor $1-1/\ell$, where $\ell = ω(mn\ln(m))$, with probability at least $1-1/m$ computes in time $O(\ell (\ln\ln (\ell) + \ln(T_0/w_{\min}) ))$ a spanning tree with weight at most $1+κ$ times the optimum weight, where $1+κ= \frac{(1+o(1))\ln(\ell m)}{\ln(\ell) -\ln (mn\ln (m))}$. Consequently, for any $ε>0$, we can choose $\ell$ in such a way that a $(1+ε)$-approximation is found in time $O((mn\ln(n))^{1+1/ε+o(1)}(\ln\ln n + \ln(T_0/w_{\min})))$ with probability at least $1-1/m$. In the special case of so-called $(1+ε)$-separated weights, this algorithm computes an optimal solution (again in time $O( (mn\ln(n))^{1+1/ε+o(1)}(\ln\ln n + \ln(T_0/w_{\min})))$), which is a significant speed-up over Wegener's runtime guarantee of $O(m^{8 + 8/ε})$.
