THESIS.bib

@COMMENT{{This file has been generated by bib2bib 1.46}}

@COMMENT{{Command line: bib2bib -ob THESIS.bib -c " ropsections:'THESIS' " bigBiblioFile.bib}}

@COMMENT{{ bigBiblioFile.bib generated by makebib.sh version }}

@COMMENT{{ concatenation of journals_ref.bib withpyblio.bib optimization.bib mypapers.bib other.bib refvulg.bib these_ref.bib philo.bib ../math/journals_ref.bib ../math/citeseer.bib ../math/books.bib }}

@COMMENT{{ date: Thu Nov 2 00:20:16 CET 2006 }}

@COMMENT{{ThisfilehasbeengeneratedbyPybliographer}}


@PHDTHESIS{schreiber1997systemes,
  AUTHOR = {Georg R. Schreiber},
  TITLE = {Syst{\`e}mes d{\'e}sordonn{\'e}s et frustr{\'e}s:
                  mod{\`e}les champ moyen et probl{\`e}mes
                  d'optimisation combinatoire},
  SCHOOL = {CEA/Saclay, SPhT},
  YEAR = {1997},
  ADDRESS = {UNIVERSITE PARIS SUD - PARIS XI},
  MONTH = {novembre},
  ROPSECTIONS = {THESIS PHYSX DISORDER REPLICA PHASE_T},
  URL = {http://theses-en-ligne.ccsd.cnrs.fr/documents/archives0/00/00/08/25/index_fr.html},
  PS = {/sci_docs/physics/papers/thesis/schreiber1997systemes.ps.gz},
  ABSTRACT = {In the present Ph.D. dissertation I present results
                  concerning disordered and frustrated models of
                  relevance in statistical mechanics and in
                  combinatorial optimization. As an application of
                  spin glass theory I study the disordered and
                  frustrated Blume-Emery-Griffiths model. The model is
                  treated in its mean-field approximation using
                  replicas. Within the Ansatz of replica-symmetry, I
                  present a complete numerical solution; I also
                  discuss effects of replica symmetry breaking. The
                  stability of the RS solution is studied and the
                  regions of instability inferred. The phase diagram
                  exhibits first and second order transitions. The
                  tricritical point is still present in the frustrated
                  model, in agreement with former work. A version of
                  the BEG model with disordered chemical potential is
                  also studied. The calculations confirm that the
                  disorder decreases the tricritical
                  temperature. Next, I consider the graph partitioning
                  problem, a combinatorial optimization problem,
                  which, from the point of view of statistical
                  mechanics is a spin glass model with the constraint
                  of zero magnetisation. I focus on the statistical
                  properties of low energy solutions generated by
                  "heuristic" algorithms designed to solve such hard
                  combinatorial optimization problems. Several
                  heuristics proposed to solve this problem were
                  implemented. Scaling laws are obtained; in
                  particular, the average cost and its variance grow
                  linearly with the number of vertices of the
                  graphs. As a consequence the cost found by the
                  heuristics is self-averaging. I suggest that this
                  property is quite general, valid for random
                  solutions, quasi-optimal solutions, and probably for
                  the optimum solutions, too. Furthermore a ranking
                  method is proposed and illustrated on an ensemble of
                  graph partitioning problems. This ranking procedure
                  takes into account the quality of the solution as
                  well as the time necessary to find that solution. In
                  the third part of this dissertation I study in
                  detail the zero-temperatures properties of spin
                  glasses on sparse random graphs with fixed
                  connectivity. Spin glasses on these graphs may be
                  considered as a more realistic approximation to real
                  spin glasses as represented by the model of
                  Sherrington and Kirkpatrick. I have designed a new
                  algorithm for finding low energy states. Second, I
                  present a method for deriving the ground state
                  energy from heuristic algorithms, even though they
                  are not guaranteed to find the optimum. Third, I
                  present a numerical test of a conjecture due to
                  Banavar, Sherrington and Sourlas, giving the large
                  volume energy density of the ground states as
                  function of the connectivity. The distribution of
                  the order parameter is found to be non-trivial, and
                  I give evidence for the presence of ultrametricity
                  for all values of the connectivity. These results
                  confirm the expectation that the remarquable
                  properties of the infinite range
                  Sherrington-Kirkpatrick model carry over to more
                  realistic models, as for example the spin glass
                  model on random graphs with finite connectivity
                  studied in the present work. }
}