Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
share
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 ≥ w_max and multiplicative cooling schedule with factor 1-1/ℓ, where ℓ = ω (mnln(m)), with probability at least 1-1/m computes in time O(ℓ (lnln (ℓ) + ln(T_0/w_min) )) a spanning tree with weight at most 1+κ times the optimum weight, where 1+κ = (1+o(1))ln(ℓ m)/ln(ℓ) -ln (mnln (m)). Consequently, for any ϵ>0, we can choose ℓ in such a way that a (1+ϵ)-approximation is found in time O((mnln(n))^1+1/ϵ+o(1)(lnln 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( (mnln(n))^1+1/ϵ+o(1)(lnln n + ln(T_0/w_min)))), which is a significant speed-up over Wegener's runtime guarantee of O(m^8 + 8/ϵ).
READ FULL TEXT