Phase Transitions in Combinatorial Optimization Problems

From MaRDI portal





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).




Cited in
(44)


Describes a project that uses

Uses Software






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)