Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM
A common approach to parallelizing simulated annealing is to generate several perturbations to the current solution simultaneously, requiring synchronization to guarantee correct evaluation of the cost function. The cost of this synchronization may be reduced by allowing inaccuracies in the cost calculations. We provide a framework for understanding the theoretical implications of this approach based on a model of processor interaction under reduced synchronization that demonstrates how errors in cost calculations occur and how to estimate them. We show how bounds on error in the cost calculations in a simulated annealing algorithm can be translated into worst-case bounds on perturbations in the parameters which describe the behavior of the algorithm.
Kenneth L. Clarkson, Elad Hazan, et al.
Journal of the ACM
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
S. Winograd
Journal of the ACM
Joseph Y. Halpern
aaai 1996