Nolte, Andreas and Schrader, Rainer
Simulated Annealing and Graph Colouring.
Combinatorics, probability & computing Vol. 10 (1).
Simulated Annealing is a very successful heuristic for various problems in combinatorial optimization. In this paper an application of Simulated Annealing to the 3-coloring problem is considered. In contrast to many good empirical results we will show for a certain class of graphs that the expected first hitting time of a proper coloring, given an arbitrary cooling scheme, is of exponential size. These results are complementary to those in "Nolte, Andreas and Schrader, Rainer (2000) A Note on the Finite Time Behaviour of Simulated Annealing", where the convergence of Simulated Annealing to an optimal solution in exponential time is proved.
- Preprinted Version
|| View Item (Login required)