Statistical mechanics methods and phase transitions in optimization problems

DOI10.1016/S0304-3975(01)00149-9zbMath1032.90075arXivcond-mat/0104428OpenAlexW2056828017WikidataQ61444464 ScholiaQ61444464MaRDI QIDQ5958800

Remi Monasson, Riccardo Zecchina, Olivier C. Martin

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cond-mat/0104428

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Phase transitions (general) in equilibrium statistical mechanics (82B26)

Related Items

Transition to coarse-grained order in coupled logistic maps: effect of delay and asymmetry, Applicability of \(n\)-vicinity method for calculation of free energy of Ising model, Dual mean field search for large scale linear and quadratic knapsack problems, An optimization algorithm inspired by the phase transition phenomenon for global optimization problems with continuous variables, Interpolating between boolean and extremely high noisy patterns through minimal dense associative memories, Statistical Physics and Network Optimization Problems, The state of SAT, Linearly constrained global optimization and stochastic differential equations, Overview: PCA Models and Issues, Uncovering the non-equilibrium stationary properties in sparse Boolean networks, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, Dual mean field annealing scheme for binary optimization under linear constraints, Generalized satisfiability problems: Minimal elements and phase transitions., Analysis of local search landscapes for \(k\)-SAT instances, Statistical mechanics of a simplified bipartite matching problem: An analytical treatment, The stable marriage problem: an interdisciplinary review from the physicist's perspective, Another look at the phenomenon of phase transition, Organization mechanism and counting algorithm on vertex-cover solutions, Local entropy as a measure for sampling solutions in constraint satisfaction problems, Phase transitions in integer linear problems, Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension, Low temperature asymptotics of spherical mean field spin glasses, Global optima results for the Kauffman \(NK\) model, Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble, Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT, New global optima results for the Kauffman \(NK\) model: Handling dependency, Complexity of learning in artificial neural networks, Proof of the local REM conjecture for number partitioning. I: Constant energy scales, On the spectral gap of spherical spin glass dynamics, Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, Critical properties of the SAT/UNSAT transitions in the classification problem of structured data, A sharp threshold for the renameable-Horn and the \(q\)-Horn properties, Threshold properties of random Boolean constraint satisfaction problems, Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem, Analytic description of the phase transition of inhomogeneous multigraphs, Spines of random constraint satisfaction problems: definition and connection with computational complexity

Uses Software

• Walksat

Cites Work

• Optimization by Simulated Annealing
• A threshold for unsatisfiability
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• On the solution of traveling salesman problems
• Length of prime implicants and number of solutions of random CNF formulae
• The stochastic traveling salesman problem: finite size scaling and the cavity prediction
• Rigorous low-temperature results for the mean field \(p\)-spins interaction model
• Phase transitions and the search problem
• The scaling window of the 2-SAT transition
• Phase coexistence and finite-size scaling in random combinatorial problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Graph bipartitioning and statistical mechanics
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• On the Travelling Salesperson Problem in Many Dimensions
• Optimization problems and replica symmetry breaking in finite connectivity spin glasses
• Entropy of theK-Satisfiability Problem
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• Exact solution of the random bipartite matching model
• Cut Size Statistics of Graph Bisection Heuristics
• Tricritical points in random combinatorics: the -SAT case
• Determining computational complexity from characteristic ‘phase transitions’
• Computer Solutions of the Traveling Salesman Problem
• Branch-and-Bound Methods: A Survey
• The complexity of theorem-proving procedures
• Martingale Inequalities and NP-Complete Problems
• A physicist's approach to number partitioning
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
• Complexity of learning in artificial neural networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item