Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm

Liers, Frauke and Palassini, Matteo and Hartmann, Alexander K. and Jünger, Michael (2003) Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm.
Published in: Physical Review B Vol. 68 (9). 094406.

Abstract

We study the Ising spin glass on random graphs with fixed connectivity z and with a Gaussian distribution of the couplings, with mean mu and unit variance. We compute exact ground states by branch-and-cut with z=4,6 and system sizes up to 1280 spins, for different values of mu . We locate the spin-glass/ferromagnet phase transition Near the phase transition, we observe a sharp change of the median running time of our implementation of the algorithm, consistent with a change from a polynomial dependence on the system size, deep in the ferromagnetic phase, to slower than polynomial in the spin-glass phase.


Actions:
Download: [img] Postscript - Preprinted Version
Download (543kB) | Preview
Download: [img] PDF - Preprinted Version
Download (360kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 21 (Google Scholar) | 11 (Web of Science)
Uncontrolled Keywords: branch-and-cut spin glasses cavity method
Subjects:
  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C90 Applications of mathematical programming

  • 82-XX Statistical mechanics, structure of matter > 82Dxx Applications to specific types of physical systems > 82D30 Random media, disordered materials (including liquid crystals and spin glasses)

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
    Institute of Computer Science > Projects > COPhy (Combinatorial Optimization in Physics)
    Related URLs:
    Deposit Information:
    ZAIK Number: zaik2003-446
    Depositing User: Frauke Liers
    Date Deposited: 19 Apr 2008 00:00
    Last Modified: 06 Feb 2012 16:10
    URI: http://e-archive.informatik.uni-koeln.de/id/eprint/446