Statistical mechanics of optimization problems

Here I will present an introduction to the results that have been recently obtained in constraint optimization of random problems using statistical mechanics techniques. After presenting the general results, in order to simplify the presentation I will describe in details the problems related to the coloring of a random graph.

• Publication year

  2006

• Venue

  Physica A-statistical Mechanics and Its Applications

• Publication date

  2006-02-15

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1016/j.physa.2006.01.033arXiv cond-mat/0602350
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Probabilistic Approach to the Random Satisfiability Problem

  2003cited by this paper
• Some remarks on the survey decimation algorithm for K-satisfiability

  2003cited by this paper
• Polynomial iterative algorithms for coloring and analyzing random graphs.

  2003cited by this paper
• Constraint Optimization and Statistical Mechanics

  2003cited by this paper
• A backtracking survey propagation algorithm for K-satisfiability

  2003cited by this paper
• Glasses, replicas and all that

  2003cited by this paper
• Spin Glasses: A Challenge for Mathematicians

  2003influential reference
• Coloring random graphs

  2002cited by this paper
• Dynamics of glassy systems

  2002cited by this paper
• On the survey-propagation equations for the random K-satisfiability problem

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• The Thermodynamic Limit in Mean Field Spin Glass Models

  2002cited by this paper
• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model

  2002cited by this paper
• On local equilibrium equations for clustering states

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Replica Bounds for Optimization Problems and Diluted Spin Systems

  2002cited by this paper
• Phase transitions and complexity in computer science: an overview of the statistical physics approach to the random satisfiability problem

  2002cited by this paper
• The Cavity Method at Zero Temperature

  2002cited by this paper
• Statistical mechanics methods and phase transitions in optimization problems

  2001cited by this paper
• Phase transitions in combinatorial problems

  2001cited by this paper
• Typical random 3-SAT formulae and the satisfiability threshold

  2000cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• Spin Glasses

  1998cited by this paper
• Critical Behavior in the Satisfiability of Random Boolean Expressions

  1994cited by this paper
• Field Theory, Disorder and Simulations

  1992cited by this paper
• Spin Glass Theory and Beyond

  1987cited by this paper
• Spin glasses for the infinitely long ranged bond Ising model and for the short ranged binary bond Ising model without use of the replica method

  1979cited by this paper
• Solution of 'Solvable model of a spin glass'

  1977cited by this paper

• The Norton–Simon hypothesis and the onset of non-genetic resistance to chemotherapy induced by stochastic fluctuations

  2012cites this paper