FINITE-TIME BEHAVIOR OF SLOWLY COOLED ANNEALING CHAINS

Authors
DESAI MP RAO VB
Citation
Mp. Desai et Vb. Rao, FINITE-TIME BEHAVIOR OF SLOWLY COOLED ANNEALING CHAINS, Probability in the engineering and informational sciences, 11(2), 1997, pp. 137-176
Citations number
33
Categorie Soggetti
Operatione Research & Management Science","Engineering, Industrial","Statistic & Probability","Operatione Research & Management Science
Journal title
Probability in the engineering and informational sciences → ACNP
ISSN journal
02699648
Volume
11
Issue
2
Year of publication
1997
Pages
137 - 176
Database
ISI
SICI code
0269-9648(1997)11:2<137:FBOSCA>2.0.ZU;2-R
Abstract
We present results on the finite-time behavior of the discrete-time, f inite-space version of the simulated annealing algorithm. The asymptot ic and finite-time behavior of the annealing algorithm under slow cool ing will be shown to depend on the largest eigenvalue of a certain mat rix. To illustrate the utility of our results, we study the slowly coo led annealing algorithm applied to the maximum matching problem and de monstrate a polynomial randomized approximation property of the algori thm.