Determining Energy Barriers by Iterated Optimization: The Two-Dimensional Ising Spin Glass.
C. Amoruso
Energy barriers determine the dynamics in many physical systems like structural glasses, disordered spin systems or proteins. Here we present an approach, which is based on subdividing the configuration space in a hierarchical manner, leading to upper and lower bounds for the energy barrier separating two configurations. The fundamental operation is to perform a constrained energy optimization, where the degree of constraintness increases with the level in the hierarchy. As application, we consider Ising spin glasses, where the energy barrier which needs to be surmounted in order to flip a compact region of spins of linear dimension $L$ are expected to scale as $L^{\psi}$. The exponent $\psi$ is very hard to estimate from experimental and simulation studies. By using the new approach, applying efficient combinatorial matching algorithms, we are able to give the first non-trivial numerical bounds $0.25 < \psi < 0.54$ for the two-dimensional Ising spin glass. %{Keywords (PACS-codes)}: Spin glasses and other random models (75.10.Nr), %numerical simulation studies (75.40.Mg). %General mathematical systems (02.10.Jf). \pacs{75.10.Nr, 75.40.Mg, 02.10.Jf}
barriers2.tex
%\documentclass[12pt]{article}
%\documentclass[aps,prl,twocolumn,superscriptaddress,showpacs]{revtex4}
\documentclass[aps,prl,twocolumn,groupedaddress,showpacs]{revtex4}

%\usepackage{epsfig}
%\usepackage{german,a4,isolatin1}
\usepackage{graphicx}

\topmargin=0.5cm                        

%\documentclass[a4paper,11pt]{article}
%\usepackage{graphicx} 
%\usepackage[latin1]{inputenc}
%\usepackage[italian]{babel}    
%\newcommand{\quer}[1]{\overline{#1}}
%\newcommand{\myscalebox}[1]{\scalebox{0.5}[0.45]{#1}}
%\newcommand{\myscaleboxb}[1]{\scalebox{0.5}[0.4]{#1}}
\newcommand{\mysection}[1]{\paragraph*{#1}}
\newcommand{\mc}{\mathcal{}}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
%\newcommand{\change}[1]{{\it #1}}
\newcommand{\change}[1]{#1}

\begin{document}
\title{
Determining Energy Barriers by Iterated Optimization: The 
Two-Dimensional Ising Spin Glass.}

\author{C. Amoruso}
\affiliation{Institut f\"ur Theoretische Physik, Universit\"at G\"ottingen,
Tammannstrasse 1, 37077 G\"{o}ttingen, Germany }
\author{A.K. Hartmann}
\affiliation{Institut f\"ur Theoretische Physik, Universit\"at G\"ottingen,
Tammannstrasse 1, 37077 G\"{o}ttingen, Germany }
\author{M.A. Moore}
\affiliation{School of Physics and Astronomy, 
University of Manchester, Manchester M13 9PL, U.K.}

\begin{abstract}
Energy barriers determine the dynamics in many physical systems like
structural glasses, disordered spin systems or proteins.
Here we present an approach, which is based on
subdividing the configuration space in a hierarchical manner, leading to
upper and lower bounds for the energy barrier separating two
configurations. The fundamental operation is to perform
a constrained energy optimization, where the degree of
constraintness increases with the level in the hierarchy.

As application, we consider Ising spin glasses, where
the energy barrier which needs to be surmounted in order to flip a
compact region of  spins of linear dimension $L$ are expected
to scale as $L^{\psi}$. The exponent $\psi$ is
very hard to estimate from experimental and simulation studies.
By using the new approach, applying efficient combinatorial 
matching algorithms,  we are able to give the first non-trivial numerical  
bounds  $0.25 < \psi < 0.54$ for the  two-dimensional  Ising spin glass.
%{\bf Keywords (PACS-codes)}: Spin glasses and other random models (75.10.Nr), 
%numerical simulation studies (75.40.Mg).
 %General mathematical systems (02.10.Jf).
\pacs{75.10.Nr, 75.40.Mg, 02.10.Jf}
\end{abstract}
\maketitle

A unifying concept in the physics of
disordered systems is the notion of energy landscapes.
\change{The dynamics of these systems is determined by (free) energy
  barriers.
Prominent examples  include spin glasses \cite{reviewSG}, structural
glasses \cite{reviewGlass} and folding of
proteins \cite{creighton1992}. The barrier problem is
also related to theoretical computer science, 
because it belongs \cite{middleton1999} to the
fundamental class of nondeterministic polynomial (NP) hard 
problems \cite{garey1979}, hence all known
algorithms determining lowest barriers take a time
growing exponentially with system size.

In this paper, we will present a hierarchical approach to calculate
minimum barriers, which is based on the application of combinatorial
optimization algorithms
\cite{opt-phys2001}. As application, we apply it to the
prototypical two-dimensional Ising spin glass, where the value of the
barrier-height exponent could not be determined so far.}

In the droplet \cite{FH1} or scaling theory of Ising spin glasses the
low-energy excitations  are compact droplets. The creation of a
droplet (a region of reversed spins) results in the formation of a
domain wall around the reversed spins and the energy of the droplet
scales as $L^\theta$ where $L$ is the linear extension of the droplet.
The system orders at low temperatures only if $\theta > 0$. The
domain wall is  fractal and has \change{size}
  $L^{d_S}$, with $d-1\leq d_S \leq d$.   The dynamics of the
system are controlled by the height of the barriers which have to be
crossed to create such droplets. It is generally assumed that the
barrier to be surmounted to create a droplet of linear extent $L$ has
an energy  which scales as $L^\psi$ where $\theta \leq \psi \leq d-1$
for dimension $d$.  The argument for these inequalities goes as
follow: the barrier must be at least as large as the energy required
to create the domain, hence $\theta \leq \psi$; the upper limit is due
to the fact that the barrier must be lower  than the energy of a
compact droplet with a non-fractal surface containing  the same number
of reversed spins.  While for a directed polymer in a random system it
was shown that  $\psi = \theta$, for Ising spin glasses $\psi$ appears
to be an independent exponent.

While many numerical studies have been done to calculate the exponent
$\theta$, we are aware of only one direct numerical estimate of $\psi$
in two dimension \cite{GCB}. It was equal to the upper bound  i.e,
$\psi = d-1$, but  only small systems were studied ($L \leq 6$).
\change{As mentioned, the barrier problem is NP hard and} it has been
difficult even to find good approximate algorithms for barriers.  This
is presumably the reason for the paucity of studies of this exponent.
Recently Drossel and Moore instead of  attempting to calculate the
barrier exactly,  placed bounds on its energy \cite{MD}. They showed
that  for the hierarchical (i.e. Berker) lattice there exists a lower
bound on $\psi$  which is the same as the upper bound $d-1$ and hence
they concluded that $\psi = d-1$.  In the same spirit as their work,
we will also obtain upper and lower bounds on the energy of the
barriers but for the more physically relevant case of the square
lattice.  Rather than study droplets, we will consider the
computationally simpler (but equivalent) task of determining  upper
and lower bounds for  the  barrier \change{separating the 
two ground states (GSs) 
related by a flip of all spins. The algorithm is based on
subdividing the configuration space in a hierarchical manner and
performing constrained energy optimizations, where the degree of
constraintness increases with the level in the hierarchy. This
approach can be applied in general to obtain minimum barrier for many 
problems, but for
the convenience of the reader, we formulate it here for the case of
the two-dimensional Ising spin glass.}

The model consists of $N=L^2$ spins $S_i = \pm 1$ on a  
square lattice with periodic boundary conditions in the $x$ direction
and free boundary conditions in the $y$ direction.
The Hamiltonian  is
\beq
H = -\sum_{\langle i j \rangle}J_{ij}S_i S_j,
\eeq
where the sum runs over all pairs of nearest 
neighbors $\langle i j \rangle$ and the $J_{ij}$ are the
quenched random spin couplings. We will consider a Gaussian
distribution of couplings with zero mean and unit width.
We define the barrier to be the energy required to invert all spins
in the GS within the context of single spin flip dynamics,
as in \cite{GCB}. Each trajectory of reversal is characterized by  
the highest maximum in the trajectory having
energy  $\delta E_{max}$, in excess of the GS energy, so that
$E_B = \min(\delta E_{max})$, where the minimum has to be computed over
all the possible trajectories.

Thus the first task is to compute the GS $\{\sigma^0\}$
of the spin glass;
in general already this problem is NP hard, but for planar graphs 
it can be mapped on to  the {\em minimum-weight perfect matching} problem,
which is solvable in polynomial time. 
The algorithms for minimum-weight perfect matchings 
\cite{MATCH-cook,MATCH-korte2000} are
among the most complicated algorithms for polynomial problems but
 the LEDA library offers a very efficient implementation
\cite{PRA-leda1999}.
For the details of the method, see
Refs.\ \onlinecite{opt-phys2001,matching-all}. 

%Let us now explain just the basic idea of the matching algorithm,
%for the details, see
%Refs. \onlinecite{bieche1980,SG-barahona82b,derigs1991}. 
%The method works for spin glasses which
%are planar graphs, this is the reason, why we apply periodic boundary
%conditions only in one direction. In the left part of
%Fig.\ \ref{fig:matching} a small 2d system with open boundary
%conditions is shown. All spins are assumed to be ``up'', hence all
%antiferromagnetic bonds are not satisfied. If one draws a dotted line
%perpendicular to all unsatisfied bonds, one ends up with the
%situation shown in the figure: all dotted lines start or end at
%frustrated plaquettes and each frustrated plaquette is connected to
%exactly one other frustrated plaquette. Each pair of
%plaquettes is then said to be {\em matched}. Now, one can consider the
%frustrated plaquettes as the vertices and all possible pairs of
%connections as the edges of a (dual) graph.
%The dotted lines are selected from the edges connecting the vertices and called
%a {\em perfect} matching, since {\em all} plaquettes are matched. 
%One can assign weights to the edges in the
%dual graph, the weights are equal to the sum of the absolute values of the
%bonds crossed by the dotted lines. The weight $\Lambda$
%of the matching is defined as the
%sum of the weights of the edges contained in the matching. As we have seen,
%$\Lambda$ measures the broken bonds, hence, the energy of the configuration
%is given by $E=-\sum_{\langle i,j\rangle} |J_{ij}|+2\Lambda$. Note
%that this holds for {\em any} configuration of the spins, since a
%corresponding matching always exists. Obtaining a ground state means 
%minimizing the total weight of the broken bonds (see right panel of
%Fig.\ \ref{fig:matching}), so one is looking
%for a {\em minimum-weight perfect matching}. This problem is solvable
%in polynomial time.
%
%\begin{figure}[htb] 
%\includegraphics[angle=0,width=0.95\columnwidth]{matching1.eps}
%\caption{2d spin glass with all spins up (left, up spins not
%  shown). Straight lines are ferromagnetic, jagged lines
%  antiferromagnetic bonds. The dotted lines
%  connect frustrated plaquettes (crosses). 
%The bonds crossed by the dotted lines
%are unsatisfied. In the right part the GS with three spins
%pointing down (all other up) is shown, 
%corresponding to a minimum number of unsatisfied bonds.}
%\label{fig:matching}
%\end{figure}
%
%The algorithms for minimum-weight perfect matchings 
%\cite{MATCH-cook,MATCH-korte2000} are
%among the most complicated algorithms for polynomial problems.
%Fortunately the LEDA library offers a very efficient implementation
%\cite{PRA-leda1999}.
%\section{Upper and Lower bounds} 
We will now show how is it possible to extract bounds on $E_B$.
\change{In general, a lower bound on the energy barriers can be
obtained, if one considers a sequence of constraints fixing some
degrees of freedeom leading from one
configuration to the other and calculating the GS under each
constraint. Here, we force a domain wall, which seperates spins having
orientation $\{\sigma^0\}$ from spin having orientation $\{-\sigma^0\}$, 
through constraining}
successive bonds along the x-axis.  Thus, for each realization of the
bonds $J_{ij}$,  a GS is first calculated with free boundary
conditions in both directions. Then ``hard'' bonds \cite{droplets}
are introduced,
i.e. bonds with a high value of the absolute strength, compatible with
the relative GS orientation of the adjacent spins, in a line
which runs from the left border to the right border. Next the sign of
exactly one hard bond on this line is inverted and the GS of
the new realization is calculated.  \change{$L$ times exactly one bond is
inverted.} The minimum of these $L$ energies
is the domain wall associated with the exponent $\theta$. The maximum
can be associate with a lower bound on $\psi$, because one is
calculating  the minimum with the highest energy in the sequence from
putting the hard bonds at successive places on the x-axis. The true
barrier height is associated with flipping one spin at a time and one
might have to climb an even higher barrier to reach the maximum domain
wall energy starting from the domain wall of minimum energy. We will
next explain how to place an upper bound on the barrier height before
discussing  the results of the numerical work.


\change{The basic idea of the general algorithm is to continue the constrained
minimization in a hierarchical manner, i.e. one introduces additional
constraints between all adjacent pairs of constrained GSs
obtained above. This is continued recursively, until the
level of changes of single degrees is reached. Hence, one obtains a
path in configuration space where the maximum energy configuration 
yields an upper bound for the  minimum energy
barrier. I.e. For the spin glass
we} do this by introducing  hard bonds along the
line corresponding to the maximum spacing between two ``adjacent'' domain
walls (either in the $x$ or the $y$ direction) and by forcing the
first domain wall through each of these bonds, see Fig.\
\ref{fig:matching}. This procedure is
repeated iteratively until two consecutive domain walls differ only by
a unique sequence of  spin flips.
Of course, since we are minimizing over a restricted set of paths,
there could be some lower path over the energy landscape, hence our
result will be an upper bound on the energy barrier. However, since
the upper bound makes an attempt to estimate the energy needed to move
the domain wall to successive places along the  x-axis by a sequence
of single spin flips, we believe the true value of $\psi$ is likely to
be nearer the upper bound than the lower bound.

\begin{figure}[htb] 
\includegraphics[angle=0,width=0.80\columnwidth]{inter1.eps}
\caption{Example showing how  the domain wall is shifted. In (a) the black
  and the gray area represent the domain walls created by changing the
  sign of two consecutive  hard bonds in the top (thick) line. The
  maximum distance between the two domain walls is determined and hard
  bonds are introduced along this line (thick line at the
  middle). Then the sign of each of these bonds is inverted exactly
  once (wiggled segment) and the new GS is calculated,
so that the  domain wall is forced   to pass through them .
In (b) the grey area now represents the configuration obtained when
changing the sign of the leftmost hard bond and calculating the new
GS. Again hard bonds are introduced along the line of
maximum distance and the new GS (c) is computed for the
realization  in which the leftmost hard bond is
inverted, as in (a). Now the distance between the two domain walls is at most one spin,
so this spin is now flipped (yielding one step of the whole
sequence) and the resulting configuration is shown in (d). 
}
\label{fig:matching}
\end{figure}


For each flipped spin the energy of the configuration is
calculated, and at the end the maximum among the $N$ energies is
considered. In this way we give an explicit rule to build a sequence
of spin-flip taking one from the GS configuration $\{\sigma^0\}$ to
$\{-\sigma^0\}$.
An example of the corresponding energy landscape sampled by this
sequence is shown in Fig. \ref{Landscape.fig}.\\
\begin{figure}[htb] 
  \includegraphics[angle=0,width=0.80\columnwidth]{Landscape.eps}
  \caption{An example of the energy landscape explored by our
    algorithm for $L=14$; the exponent $\psi$ is  associated with the scaling of the maximum energy found in the sequence.
  }
  \label{Landscape.fig}
\end{figure}
%
One has to be careful to exclude the  domain walls
which are not crossing the system and for which the width $L$
is not an appropriate measure of their scale. Those configurations can appear in the first
steps of the algorithm described above because of the use of free
boundary conditions. 
Fortunately most of the domain walls do span the system. We have restricted our analysis to
 those configurations.
%
\begin{figure}[htb] 
  \includegraphics[angle=0,width=0.80\columnwidth]{barriers.eps}
  \caption{Upper line: maximum over $L$ energies in the sequence from 
    putting hard bonds at successive places on the $x$ axis  plotted  as a function of the system size.
    Lower line: maximum energy in the sequence of single spin-flip
    built as explained above.
  }
  \label{fig:barriers}
\end{figure}
%

We applied our method for system sizes in the range $8 < L < 40$,
and for each $L$ used  $1000$ independent realizations of the bonds $J_{ij}$.
The two quantities $\Delta
E_{min}$ (the lower bound) and $\Delta E_{max}$ (the upper bound) as a function of system size are shown
in Fig. \ref{fig:barriers}. Both quantities can  be fitted by an
algebraic function $\sim L^{\psi}$, where $\psi_{lw} = 0.25 \pm 0.01$
and $\psi_{up} =  0.54 \pm0.01$. 
There could of course be a
procedure to obtain a better path in
configuration space, yielding a barrier which grows more slowly than
$L^{0.54}$. However this is to our knowledge the only numerical estimate of
the energy barriers exponent giving an upper bound different from the
trivial one $d-1$.

There are many experimental estimate of $\psi$ in the literature, and
there is disagreement as to its value.  Dekker et al \cite{EXP1}
reported experimental verification of activated dynamics in a $d=2$
system obtaining $\psi = 0.9$.  Schins et al. \cite{EXP2} find $\psi =
1.0 \pm 0.1$ by studying aging via the low-frequency ac susceptibility
giving credence to the claim that $\psi$ is equal to its upper bound.
However, Dupius et al \cite{EXP3} extracted $0.3 < \psi < 0.7$ in
$d=2$ and $\psi \sim 1.1$ in $d=3$.  The numerical study of Gawron et
al. gave  $\psi = 0.9 \pm 0.1$ in 2 dimension, while that of Berthier
and Bouchaud \cite{BerthBouch3d} had $\psi \sim 1.0$ and $\psi \sim
2.3$ in 3 and 4 dimensions respectively.  We remark that our
optimization algorithms do not suffer from equilibration problems,
they are exact and they allow the study of large systems at least in
two dimensions. Besides, by iteratively applying our matching
algorithm, we are producing large scale changes to the domain wall,
which is how $\psi$ can become less than $d-1$. (We have studied the
barrier associated with a straight domain wall and found that the
expected linear behavior is approached  by $L\sim 40$).
%

In Figs.\ \ref{distrib_LB.fig} and \ref{distrib_UB.fig}  
the rescaled probability
distributions of the barriers heights corresponding to both the lower
and upper bounds which we have found,  averaged over the disorder, is
shown for different sizes $L$: in both cases it seems to approach  a
fixed shape in the thermodynamical limit (although the approach to a
scaling collapse is faster for the upper bound).

\begin{figure}[t] 
  \includegraphics[angle=0,width=0.75\columnwidth]{P_DE_lower.eps}
  \caption{Rescaled probability distribution of the lower bound for the
barriers heights with $\psi = 0.25$}
  \label{distrib_LB.fig}
\end{figure}
\begin{figure}[htb] 
  \includegraphics[angle=0,width=0.80\columnwidth]{P_DE_upper.eps}
  \caption{Rescaled probability distribution of the upper bound for the
barriers heights corresponding to $\psi = 0.54$}
  \label{distrib_UB.fig}
\end{figure}

Notice that both these distributions have long tails indicating the
existence of some very large barriers, 
which implies that some spin configurations could be very long-lived.
%


%
%
%Besides one can show that if the lower bound  follows a power law
%scaling, then the same holds for tail of the energy barrier
%distribution. Consider in fact the probability distribution of domain
%walls passing through each bond in turn for a given bond realization,
%$P_L(E)$. The probability that all the $L$ values are less than $E$ is 
%$Q(E) = [\int_0^E dJ P(J)]^L \simeq exp^{-L\int_E^{\infty} dJ P(J)}$,
%so that $P_L(E) = \frac{dQ}{dE} = L Q(E)P(E)$. Now if we suppose that,
%for large $J$,$P(J) \sim J^{-(1+\alpha)}$, then $P_L(E)$ has a peak $E
%\sim L^{-\alpha} = L^{\psi_{LB}}$. This means the $\alpha =
%\frac{1}{\alpha} \simeq 4$.

 

We also investigated geometrical properties of the domain walls
corresponding to the energy barriers.
The boundaries of the low-energy excitations are fractal with a
an average length  along the perimeter of order  $P \sim L^{d_S}$,
with $d-1 \leq d_S \leq d$. 
%
\begin{figure}[htb] 
  \includegraphics[angle=0,width=0.80\columnwidth]{surface.eps}
  \caption{The perimeter (length) of the surface of the domain wall corresponding to the upper bound (maximum)
energy.
 Data are fitted very well by
    a power law $P \sim L^{d_S}$ with $d_S = 1.27 \pm 0.01$.}
  \label{fig:perimeter}
\end{figure}
%
We have computed the fractal dimension of the domain wall $d_S$ corresponding
to the configuration of maximum energy. We have found the
interesting result that $d_S = 1.27 \pm 0.01$, which is the same value 
 for domain walls of minimum energy. 



%This feature
%suggests the following speculation: in the droplet theory, the
%smallness of  $L^{\theta}$ compared to the {\em naive } estimate
%$L^{d-1}$ for the free energy of an overturned region of spins of size
%$L$ is due to large cancellation from the energetic term $\sim L^{\frac{d_s}{2}}$
%and the entropic term $\sim \sigma(T)L^{\frac{d_s}{2}}$. At zero
%temperature this is no more true and since  the
%carachteristic lenght of the configuration  corresponding to the maximum
%energy is the same as the one corresponding to the minimum energy; 
%this could imply  $\psi = \frac{d_s}{2}$,  which is consistent
%with our estimation of $\psi$ and $d_s$.


%**************************************************************************

%**************************************************************************
To conclude we \change{have introduced a hierarchical algorithm to compute
upper and lower bounds on energy barriers in disordered
system. Applying the algorithm to two-dimensional Ising spin glasses,
we find that the minimum barrier energy}
is bounded above by the scale
$L^{0.54}$ and below by $L^{0.24}$. Our numerical upper bound is
significantly less than the rigorous upper bound (and the value for
the hierarchical lattice), $d-1$. Hence, we suspect that 
$\psi$ is an  entirely non-trivial exponent. At the present time there
seems no theoretical approach which might explain a non-trivial value
of $\psi$

%**************************************************************************

%**************************************************************************
The authors have obtained financial support from the
{\em VolkswagenStiftung} (Germany) within the program
``Nachwuchsgruppen an Universit\"aten'',
\change{from the Paderborn Center
for Parallel Computing in German,
 and from the European Community
via the DYGLAGEMEM, High-Level Scientific
Conferences (HLSC) and the  ``Exystence'' programs.}
%The simulations were performed at the Paderborn Center
%for Parallel Computing in Germany and on a workstation
%cluster at the Institut f\"ur Theoretische Physik, Universit\"at
%G\"ottingen, Germany.


\begin{thebibliography}{99}
\bibitem{reviewSG}  Reviews on spin glasses can be found in:
    K. Binder and A.P. Young, Rev. Mod. Phys. {\bf 58}, 801 (1986); M. Mezard,
    G. Parisi, M.A. Virasoro, {\it Spin glass theory and beyond}\/, (World
    Scientific, Singapore 1987); K.H. Fisher and J.A. Hertz, {\em Spin
    Glasses}\/, (Cambridge University Press, Cambridge 1991); A.P. Young
    (ed.), {\em Spin glasses and random fields}\/, (World Scientific,
    Singapore 1998).

\bibitem{reviewGlass} Reviews on glasses can be found in C.A. Angell,
  Science {\bf 267}, 1924 (1995); P.G. DeBenedetti, {\em Metastable
    liquids}, (Princeton University Press, 1996);  S. Franz,
  S.C. Glotzer, and S. Sastry (eds.),  {\em Unifying Concepts in Glass
    Physics}, J. Phys. Cond. Matt. {\bf 12}, 6295-6682 (2000)

\bibitem{creighton1992} T.E. Creighton (ed.), {\em Protein folding},
  (Freemann, New York 1992).

\bibitem{middleton1999} A.A. Middleton, Phys. Rev. E {\bf 59}, 2571 (1999).

\bibitem{garey1979} M. R. Garey and D. S. Johnson, {\it Computers and
    intractability} (Freeman, San Francisco, 1979)

\bibitem{opt-phys2001}
    A. K. Hartmann and H. Rieger, {\em Optimization Algorithms in Physics}\/,
    (Wiley-VCH, Berlin 2001).


\bibitem{FH1}
    D.S. Fisher and D.A.Huse, Phys. Rev. B {\bf38}, 273 and 386 (1988).

\bibitem{GCB}
  T.R. Gawron, M. Cieplak and J.R. Banavar
  J. Phys. A:Math. Gen. {\bf 24} L127 (1991)

\bibitem{MD}
  B. Drossel and M.A. Moore, Phys. Rev. B \textbf{70}, 064412 (2004).

%\bibitem{cook-korte}
%  W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver,
%  {\it Combinatorial Optimization}\/, (John Wiley \& Sons,  New York
%  1998);
%B. Korte and J. Vygen, {\em Combinatorial Optimization - Theory and
%Algorithms}\/, (Springer, Heidelberg 2000).

\bibitem{MATCH-cook}
  W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver,
  {\it Combinatorial Optimization}\/, (John Wiley \& Sons,  New York 1998).

\bibitem{MATCH-korte2000}
B. Korte and J. Vygen, {\em Combinatorial Optimization - Theory and
Algorithms}\/, (Springer, Heidelberg 2000).

\bibitem{PRA-leda1999}  K. Mehlhorn and St. N\"aher, 
    {\em The LEDA Platform of Combinatorial and Geometric Computing}\/
    (Cambridge University Press, Cambridge 1999); \\
    see also  http://www.algorithmic-solutions.de 

\bibitem{droplets} A. K. Hartmann and M. A. Moore, 
Phys. Rev. Lett. {\bf 90}, 127201 (2003).

\bibitem{matching-all}
   I. Bieche, R. Maynard, R. Rammal, and J.P. Uhry, J. Phys. A {\bf 13}, 2553
    (1980);  F. Barahona, R. Maynard, R. Rammal, and
J.P. Uhry, {\it J. Phys. A}\/ {\bf 15}, 673 (1982);
   U. Derigs and A. Metz, Math. Prog. {\bf 50}, 113 (1991).

%\bibitem{bieche1980}
%    I. Bieche, R. Maynard, R. Rammal, and J.P. Uhry, J. Phys. A {\bf 13}, 2553
%    (1980).
%
%\bibitem{SG-barahona82b} F. Barahona, R. Maynard, R. Rammal, and
%J.P. Uhry, {\it J. Phys. A}\/ {\bf 15}, 673 (1982).
%
%\bibitem{derigs1991}
%   U. Derigs and A. Metz, Math. Prog. {\bf 50}, 113 (1991).

\bibitem{EXP1}
C. Dekker, A.F.M. Arts and H.W de Wijn, and A.J. van Duyneveldt and
J.A. Mydosh, Phys. Rev. Lett. {\bf 61}, 1780 (1988)

\bibitem{EXP2}
  A.G. Schins, E.M. Dons, A.F.M.Arts,  H.W. de Wijn, E. Vincent,
  L.Leylekian and J. Hamman, Phys. Rev B {\bf 48}, 16524 (1993)

\bibitem{EXP3}
  V.Dupius, E. Vincent, J.P. Bouchaud, J.Hamman, A. Ito and H. Aurga
  Katorim,  Phys Rev B {\bf 64}, 174204
  

\bibitem{BerthBouch3d}
 L. Berthier and J-P. Bouchaud Phys. Rev. B {\bf 66}, 054404 (2002)


%\bibitem{carter2002}
%A.C. Carter, A.J. Bray, and M.A. Moore,
%Phys. Rev. Lett. 88, 077201 (2002).
%Aspect-Ratio Scaling and The Stiffness Exponent for Ising Spin Glasses 

%\bibitem{McM}
%W.L. McMillan, J. Phys. C \textbf{17}, 3179 (1984).

%\bibitem{BM}
%A.J. Bray and M.A. Moore, in \textit{ Glassy Dynamics and Optimization},
%edited by J. L. van Hemmen and I. Morgenstern, (Springer, Berlin, 1986).

%\bibitem{FH}
%D.S. Fisher and D.A. Huse, Phys. Rev. Lett. \textbf{56}, 1601 (1986);
%Phys. Rev. B \textbf{ 38}, 386 (1988).

%\bibitem{BrayMoore} A.J.~Bray and M.A.~Moore: J.\ Phys.\ C
    {\bf 14},   L463 (1984).

    



%\bibitem{droplet2d} A.K. Hartmann and M.A. Moore, 
%Phys. Rev. Lett. {\bf 90}, 127201 (2003).
%Corrections to Scaling are Large for Droplets in Two-Dimensional Spin Glasses


\bibitem{Barahona82} F.~Barahona, R.~Maynard, R.~Rammal and J.~P.~Uhry:
    J.\ Phys.\ A {\bf 15},  673 (1982).


\bibitem{MaynardR} R.~Maynard and R.~Rammal:
    J.\ Phys.\ Lett.\ (France) {\bf 43} (1982) L347.
\bibitem{Ozeki90} Y.Ozeki: J.\ Phys.\ Soc.\ Jpn.\ {\bf 59}, 
  3531 (1990).





%\bibitem{AMMP}

 % C. Amoruso, E. Marinari, O.C. Martin and A. Pagnani
%Phys. Rev. Lett. {\bf 91},  08720, (2003)


%\bibitem{numrec1995}
%   W.H. Press, S.A. Teukolsky, W.T. Vetterling and B.P. Flannery,
%   {\em
%    Numerical Recipes in C}\/, (Cambridge University Press, Cambridge
%  1995).






\end{thebibliography}
\end{document}

cond-mat0502201.extracted_bib
\begin{thebibliography}{99}
\bibitem{reviewSG}  Reviews on spin glasses can be found in:
    K. Binder and A.P. Young, Rev. Mod. Phys. {\bf 58}, 801 (1986); M. Mezard,
    G. Parisi, M.A. Virasoro, {\it Spin glass theory and beyond}\/, (World
    Scientific, Singapore 1987); K.H. Fisher and J.A. Hertz, {\em Spin
    Glasses}\/, (Cambridge University Press, Cambridge 1991); A.P. Young
    (ed.), {\em Spin glasses and random fields}\/, (World Scientific,
    Singapore 1998).

\bibitem{reviewGlass} Reviews on glasses can be found in C.A. Angell,
  Science {\bf 267}, 1924 (1995); P.G. DeBenedetti, {\em Metastable
    liquids}, (Princeton University Press, 1996);  S. Franz,
  S.C. Glotzer, and S. Sastry (eds.),  {\em Unifying Concepts in Glass
    Physics}, J. Phys. Cond. Matt. {\bf 12}, 6295-6682 (2000)

\bibitem{creighton1992} T.E. Creighton (ed.), {\em Protein folding},
  (Freemann, New York 1992).

\bibitem{middleton1999} A.A. Middleton, Phys. Rev. E {\bf 59}, 2571 (1999).

\bibitem{garey1979} M. R. Garey and D. S. Johnson, {\it Computers and
    intractability} (Freeman, San Francisco, 1979)

\bibitem{opt-phys2001}
    A. K. Hartmann and H. Rieger, {\em Optimization Algorithms in Physics}\/,
    (Wiley-VCH, Berlin 2001).


\bibitem{FH1}
    D.S. Fisher and D.A.Huse, Phys. Rev. B {\bf38}, 273 and 386 (1988).

\bibitem{GCB}
  T.R. Gawron, M. Cieplak and J.R. Banavar
  J. Phys. A:Math. Gen. {\bf 24} L127 (1991)

\bibitem{MD}
  B. Drossel and M.A. Moore, Phys. Rev. B \textbf{70}, 064412 (2004).

%\bibitem{cook-korte}
%  W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver,
%  {\it Combinatorial Optimization}\/, (John Wiley \& Sons,  New York
%  1998);
%B. Korte and J. Vygen, {\em Combinatorial Optimization - Theory and
%Algorithms}\/, (Springer, Heidelberg 2000).

\bibitem{MATCH-cook}
  W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver,
  {\it Combinatorial Optimization}\/, (John Wiley \& Sons,  New York 1998).

\bibitem{MATCH-korte2000}
B. Korte and J. Vygen, {\em Combinatorial Optimization - Theory and
Algorithms}\/, (Springer, Heidelberg 2000).

\bibitem{PRA-leda1999}  K. Mehlhorn and St. N\"aher, 
    {\em The LEDA Platform of Combinatorial and Geometric Computing}\/
    (Cambridge University Press, Cambridge 1999); \\
    see also  http://www.algorithmic-solutions.de 

\bibitem{droplets} A. K. Hartmann and M. A. Moore, 
Phys. Rev. Lett. {\bf 90}, 127201 (2003).

\bibitem{matching-all}
   I. Bieche, R. Maynard, R. Rammal, and J.P. Uhry, J. Phys. A {\bf 13}, 2553
    (1980);  F. Barahona, R. Maynard, R. Rammal, and
J.P. Uhry, {\it J. Phys. A}\/ {\bf 15}, 673 (1982);
   U. Derigs and A. Metz, Math. Prog. {\bf 50}, 113 (1991).

%\bibitem{bieche1980}
%    I. Bieche, R. Maynard, R. Rammal, and J.P. Uhry, J. Phys. A {\bf 13}, 2553
%    (1980).
%
%\bibitem{SG-barahona82b} F. Barahona, R. Maynard, R. Rammal, and
%J.P. Uhry, {\it J. Phys. A}\/ {\bf 15}, 673 (1982).
%
%\bibitem{derigs1991}
%   U. Derigs and A. Metz, Math. Prog. {\bf 50}, 113 (1991).

\bibitem{EXP1}
C. Dekker, A.F.M. Arts and H.W de Wijn, and A.J. van Duyneveldt and
J.A. Mydosh, Phys. Rev. Lett. {\bf 61}, 1780 (1988)

\bibitem{EXP2}
  A.G. Schins, E.M. Dons, A.F.M.Arts,  H.W. de Wijn, E. Vincent,
  L.Leylekian and J. Hamman, Phys. Rev B {\bf 48}, 16524 (1993)

\bibitem{EXP3}
  V.Dupius, E. Vincent, J.P. Bouchaud, J.Hamman, A. Ito and H. Aurga
  Katorim,  Phys Rev B {\bf 64}, 174204
  

\bibitem{BerthBouch3d}
 L. Berthier and J-P. Bouchaud Phys. Rev. B {\bf 66}, 054404 (2002)


%\bibitem{carter2002}
%A.C. Carter, A.J. Bray, and M.A. Moore,
%Phys. Rev. Lett. 88, 077201 (2002).
%Aspect-Ratio Scaling and The Stiffness Exponent for Ising Spin Glasses 

%\bibitem{McM}
%W.L. McMillan, J. Phys. C \textbf{17}, 3179 (1984).

%\bibitem{BM}
%A.J. Bray and M.A. Moore, in \textit{ Glassy Dynamics and Optimization},
%edited by J. L. van Hemmen and I. Morgenstern, (Springer, Berlin, 1986).

%\bibitem{FH}
%D.S. Fisher and D.A. Huse, Phys. Rev. Lett. \textbf{56}, 1601 (1986);
%Phys. Rev. B \textbf{ 38}, 386 (1988).

%\bibitem{BrayMoore} A.J.~Bray and M.A.~Moore: J.\ Phys.\ C
    {\bf 14},   L463 (1984).

    



%\bibitem{droplet2d} A.K. Hartmann and M.A. Moore, 
%Phys. Rev. Lett. {\bf 90}, 127201 (2003).
%Corrections to Scaling are Large for Droplets in Two-Dimensional Spin Glasses


\bibitem{Barahona82} F.~Barahona, R.~Maynard, R.~Rammal and J.~P.~Uhry:
    J.\ Phys.\ A {\bf 15},  673 (1982).


\bibitem{MaynardR} R.~Maynard and R.~Rammal:
    J.\ Phys.\ Lett.\ (France) {\bf 43} (1982) L347.
\bibitem{Ozeki90} Y.Ozeki: J.\ Phys.\ Soc.\ Jpn.\ {\bf 59}, 
  3531 (1990).





%\bibitem{AMMP}

 % C. Amoruso, E. Marinari, O.C. Martin and A. Pagnani
%Phys. Rev. Lett. {\bf 91},  08720, (2003)


%\bibitem{numrec1995}
%   W.H. Press, S.A. Teukolsky, W.T. Vetterling and B.P. Flannery,
%   {\em
%    Numerical Recipes in C}\/, (Cambridge University Press, Cambridge
%  1995).






\end{thebibliography}