Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-089 | 26th October 2004 00:00

Simulated Annealing Beats Metropolis in Combinatorial Optimization


Authors: Ingo Wegener
Publication: 26th October 2004 13:59
Downloads: 4268


The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all temperatures has been discussed by Jerrum and Sinclair (1996) as"an outstanding open problem". This problem is solved here. The examples are simple instances of the well-known minimum spanning tree problem. Moreover, it is investigated which instances of the minimum spanning tree problem can be solved efficiently by simulated annealing. This is motivated by the aim to develop further methods to analyze the simulated annealing process.

ISSN 1433-8092 | Imprint