Phase Transitions in Combinatorial Optimization Problems
Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to statistical mechanics (82-02) Equilibrium statistical mechanics (82B99) Combinatorial optimization (90C27) Applications of mathematical programming (90C90)
The study of random combinatorial optimization problems witnessed a spectacular development in the last few years. Possibly the strongest impulse came from the introduction in this field of ideas based on statistical mechanics, and more specifically on the physics of diluted, mean field, spin glass models. The book under review represents a pedagogical introduction to these ideas and to some of their practical applications, and will be of great help to newcomers in this field, both coming from a physics or from a computer science background. As an example of combinatorial optimization problem, think of the well known Traveling Salesman Problem (TSP): given \(N\) cities \(c_i\), \(i=1,\ldots,N\) and the distances \(d_{ij}\) between them, find the shortest closed path which visits all the cities and ends at the starting point. More generally, one wishes to minimize some ``cost function which depends on many (say, \(N\)) variables (say, boolean variables) and on some additional ``interaction parameters (in the TSP, the entries of the matrix \(d_{ij}\)). In applications, it is often of interest to consider the case where the ``interaction parameters are random variables (in this case, one says one is studying typical case complexity rather than worst case complexity). In the statistical physics language, the cost function corresponds to the Hamiltonian \(H\), the ``interaction parameters to (possibly random) couplings between degrees of freedom and the minimization of \(H\) is naturally seen as a zero-temperature limit. This way some natural optimization problems, like the so-called K-SAT, can be exactly mapped into statistical mechanics models with quenched disorder (typically, spin glasses on random diluted graphs) and concepts like glassiness and breaking of replica symmetry become of central importance. Given the tight link with statistical mechanics, it is not surprising that optimization problems show in the large-\(N\) limit phase transition analogous to those one observes in physical systems. Concepts like critical exponents, finite-size scaling, universality etc. arise therefore very naturally in this context. There are two broad classes of questions one can ask on these models: questions about the number of minimizing solutions and about their geometrical structure, and questions about the time required by a given algorithm to find these solutions. Broadly speaking, in statistical mechanics language this corresponds to the distinction between equilibrium and dynamical properties. Both types of questions are treated in the book. In particular, the structure of the space of solution turns out in many cases to be an ultrametric (hierarchical) one, as is also the case for the low-energy configurations of spin glass systems. This is a quite interdisciplinary field of research, involving for instance probability theory, graph theory, combinatorics and of course statistical mechanics. The first 5 chapters of the book are a pedagogical and informal introduction to optimization algorithms, random graphs, complexity theory (i.e., questions of the type: how to classify optimization problems according to their hardness? does a given optimization problem admit an algorithm which finds an optimal solution in a running time polynomial in \(N\)?) and statistical mechanics of Ising systems with randomness. In the rest of the book, the authors concentrate for simplicity on two specific optimization problems: \textit{vertex coloring} and \textit{K-satisfiability} (K-SAT).
- Statistical mechanics methods and phase transitions in optimization problems
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- An asymptotical study of combinatorial optimization problems by means of statistical mechanics
- Statistical mechanics: a general approach to combinatorial optimization
- Phase transitions in parameter rich optimization problems
- Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
- Refining the phase transition in combinatorial search
- Phase transitions and complexity in computer science: An overview of the statistical physics approach to the random satisfiability problem
- Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph.
- Publication:4488030
- Dual mean field search for large scale linear and quadratic knapsack problems
- Notes on computational-to-statistical gaps: predictions using statistical physics
- Measuring instance difficulty for combinatorial optimization problems
- Critical phenomena in a collective computation algorithm for combinatorial optimization problems
- Application of statistical mechanics to combinatorial optimization problems: the chromatic number problem and \(q\)-partitioning of a graph.
- A review of message passing algorithms in estimation of distribution algorithms
- From decidability to undecidability by considering regular sets of instances
- Leveraging cluster backbones for improving MAP inference in statistical relational models
- Maximum independent sets on random regular graphs
- Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
- Free energy rates for a class of very noisy optimization problems
- Computational complexity, phase transitions, and message-passing for community detection
- scientific article; zbMATH DE number 4133843 (Why is no real title available?)
- Criticality and heterogeneity in the solution space of random constraint satisfaction problems
- Research on solution space of bipartite graph vertex-cover by maximum matchings
- Random multi-overlap structures for optimization problems
- Statistical physics and network optimization problems
- Cost distributions in large combinatorial optimisation problems
- NONLINEAR TIME SERIES PREDICTION BASED ON A POWER-LAW NOISE MODEL
- Information, Physics, and Computation
- Mathematical foundation of quantum annealing
- Propagation of external regulation and asynchronous dynamics in random Boolean networks
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- Percolation on interdependent networks with a fraction of antagonistic interactions
- Exploring the role of graph spectra in graph coloring algorithm performance
- scientific article; zbMATH DE number 1735139 (Why is no real title available?)
- Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
- Using cellular automata on a graph to model the exchanges of cash and goods
- Network meta-analysis: a statistical physics perspective
- Generalized \(K\)-core percolation in networks with community structure
- Two faces of greedy leaf removal procedure on graphs
- On the critical exponent of the 5D random-field Ising model
- Constructing concrete hard instances of the maximum independent set problem
- Phase transitions in parameter rich optimization problems
- The number of matchings in random graphs
- Statistical mechanics and stability of a model eco-system
- Phase transitions in machine learning.
- Scaling and universality in continuous length combinatorial optimization
- scientific article; zbMATH DE number 2243360 (Why is no real title available?)
- Geometric properties of satisfying assignments of random ε-1-in-kSAT
- Replica theory for Levy spin glasses
- Statistical mechanics methods and phase transitions in optimization problems
- Multi-hop generalized core percolation on complex networks
- Glassy behavior and jamming of a random walk process for sequentially satisfying a constraint satisfaction formula
This page was built for publication: Phase Transitions in Combinatorial Optimization Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463601)