Randomization in Discrete Optimization: Annealing Algorithms

Sanguthevar Rajasekaran

ABSTRACT

Annealing algorithms have been employed extensively in the past decade to solve myriads of optimization problems. Several intractable problems such as the traveling salesman problem, graph partitioning, and circuit layout have been solved to get satisfactory results. In this article we survey convergence results known for annealing algorithms. In particular we deal with simulated annealing and nested annealing.