Universität zu Köln

Nolte, Andreas and Schrader, Rainer (2001). Simulated Annealing and Graph Colouring. Combinatorics, probability & computing, 10 (1). 29 -40. Cambridge Univ. Press.

Preview

PDF zaik1999-348.pdf - Draft Version Download (234kB) | Preview

Abstract

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Nolte, Andreas UNSPECIFIED UNSPECIFIED UNSPECIFIED Schrader, Rainer UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548345
Journal or Publication Title:	Combinatorics, probability & computing
Volume:	10
Number:	1
Page Range:	29 -40
Date:	2001
Publisher:	Cambridge Univ. Press
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54834