  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 = \omega (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+\kappa$ times the optimum weight, where $1+\kappa =
\frac{(1+o(1))\ln(\ell m)}{\ln(\ell) -\ln (mn\ln (m))}$. Consequently, for any
$\epsilon>0$, we can choose $\ell$ in such a way that a
$(1+\epsilon)$-approximation is found in time
$O((mn\ln(n))^{1+1/\epsilon+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+\epsilon)$-separated weights, this algorithm computes an optimal solution
(again in time $O( (mn\ln(n))^{1+1/\epsilon+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/\epsilon})$.
