Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem

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 (Automata, Languages and Programming, ICALP, Berlin, 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≥ w_max and multiplicative cooling schedule with factor 1 - 1 / ℓ , where ℓ= ω(mnln (m)) , with probability at least 1 - 1 / m computes in time O(ℓ(ln ln (ℓ) + ln (T/ 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)(ln ln n+ ln (T/ 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)(ln ln n+ ln (T/ w_min)))), which is a significant speed-up over Wegener’s runtime guarantee of O(m^8+8/ϵ) . Our tighter upper bound also admits the result that in some situations a hybridization of simulated annealing and the (1 + 1) EA can lead to stronger runtime guarantees than either algorithm alone.