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

Benjamin Doerr, Amirhossein Rajabi, Carsten Witt

We prove that Simulated Annealing with an appropriate cooling schedule computes arbitrarily tight constant-factor approximations to the minimum spanning tree problem in polynomial…