The first such result to be published is in [GeGe84]. The resulting bound is
SNx (Cma, CmJn)
Tk 2 Nx(C Eq. 2.12
log(k)
k>2
where Cm,a and Cmin are the maximum and minimum values respectively of C(i) for i e S
and N = card(S). Thus, Cmi,, is the desired Cop.
The annealing schedule bound established in [MiRo85] is more refined than that of
Eq. 2.12. It is given by
rL
Tk > lo Eq. 2.13
log(k)
k>2
where r is the radius of the graph defining the accessible state neighborhoods of the next
state generation mechanism (i.e. the {S,} where S, c S is defined in Eq. 2.5), and L is a
constant which bounds the local slope of the cost function. Specifically, r and L are given
by
r= min max d(i,j) Eq. 2.14
iES-Sma jE S
where d(i,j) is the distance ofj from i, measured by the minimum number of state trans-
itions required to arrive at j starting at i, where Sma, c S is the set of local maxima of C
and
L= max max I C(j)- C(i) I. Eq. 2.15
i eS j S
Note that in the special case S, = S for all i e S, then Eq. 2.14 and Eq. 2.15 reduce to r= 1
and L = Cma Cmin respectively, and substitution into Eq. 2.13 yields
Tk (Cmax Cmin)
Tk 2 Eq. 2.16
log(k)
The Eq. 2.16 result is smaller than that of Eq. 2.12 by the factor 1/N.