Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics

A concise, comprehensive introduction to the topic of statistical physics of combinatorial optimization, bringing together theoretical concepts and algorithms from computer science with analytical methods from physics. The result bridges the gap between statistical physics and combinatorial optimization, investigating problems taken from theoretical computing, such as the vertex--cover problem, with the concepts and methods of theoretical physics. The authors cover rapid developments and analytical methods that are both extremely complex and spread by word--of--mouth, providing all the necessary basics in required detail. Throughout, the algorithms are shown with examples and calculations, while the proofs are given in a way suitable for graduate students, post--docs, and researchers. Ideal for newcomers to this young, multidisciplinary field.

Table of Contents:
Preface. 1 Introduction. 1.1 Two examples of combinatorial optimization. 1.2 Why study combinatorial optimization using statistical physics? 1.3 Textbooks. Bibliography. 2 Algorithms. 2.1 Pidgin Algol. 2.2 Iteration and recursion. 2.3 Divide-and-conquer. 2.4 Dynamic programming. 2.5 Backtracking. Bibliography. 3 Introduction to graphs. 3.1 Basic concepts and graph problems. 3.2 Basic graph algorithms. 3.3 Random graphs. Bibliography. 4 Introduction to complexity theory. 4.1 Turing machines. 4.2 Church's thesis. 4.3 Languages. 4.4 The halting problem. 4.5 Class P. 4.6 Class NP. 4.7 Definition of NP-completeness. 4.8 NP-complete problems. 4.9 Worst-case vs. typical-case complexity. Bibliography. 5 Statistical mechanics of the Ising model. 5.1 Phase transitions. 5.2 Some general notes on statistical mechanics. 5.3 The Curie-Weiss model of a ferromagnet. 5.4 The Ising model on a random graph. Bibliography. 6 Algorithms and numerical results for vertex covers. 6.1 Definitions. 6.2 Heuristic algorithms. 6.3 Branch-and-bound algorithm. 6.4 Results: Covering random graphs. 6.5 The leaf-removal algorithm. 6.6 Monte Carlo simulations. 6.7 Backbone. 6.8 Clustering of minimum vertex covers. Bibliography. 7 Statistical mechanics of vertex covers on a random graph. 7.1 Introduction. 7.2 The first-moment bound. 7.3 The hard-core lattice gas. 7.4 Replica approach. Bibliography. 8 The dynamics of vertex-cover algorithms. 8.1 The typical-case solution time of a complete algorithm. 8.2 The dynamics of generalized leaf-removal algorithms. 8.3 Random restart algorithms. Bibliography. 9 Towards new, statistical-mechanics motivated algorithms. 9.1 The cavity graph. 9.2 Warning propagation. 9.3 Belief propagation. 9.4 Survey propagation. 9.5 Numerical experiments on random graphs. Bibliography. 10 The satisfiability problem. 10.1 SAT algorithms. 10.2 Phase transitions in random K-SAT. 10.3 Typical-case dynamics of RandomWalkSAT. 10.4 Message-passing algorithms for SAT. Bibliography. 11 Optimization problems in physics. 11.1 Monte Carlo optimization. 11.2 Hysteric optimization. 11.3 Genetic algorithms. 11.4 Shortest paths and polymers in random media. 11.5 Maximum flows and random-field systems. 11.6 Submodular functions and free energy of Potts model. 11.7 Matchings and spin glasses. Bibliography. Index.

About the Author :
Alexander K. Hartmann, Ph.D. (1998) from the University of Heidelberg, Diplom (1993) from the University of Duisburg. Since January 2003, Head of the Junior Research group "Complex Ground States of Disordered Systems at the University of Gottingen funded by the Volkswagen Stiftung. 1998-2003, Research Assistant in Prof. Annette Zippelius' group at the University of Gottingen. 2001, Visiting Scientist at the University of California, Santa Cruz and the Ecole Normale Superieure. His research interests are the computer simulations of spin glasses, random field systems and diluted antiferromagnets, gas atoms inside polymer systems, combinatorial optimization problems, random surfaces and surface sputtering, and biophysics (RNA secondary structures and sequence alignment). Martin Weigt, born 1970 in Berlin, Germany; Ph.D. (1998) from Otto-von-Guericke University, Magdeburg, Diplom (1993) from Humboldt University Berlin. Since 1999, Research Assistant in Prof. Annette Zippelius' group at the University of Gottingen. In 2000, 2001, and 2002, Visiting Scientist at the International Centre of Theoretical Physics, Trieste, Italy. His research interests are statistical mechanics of disordered systems and application in random combinatorics and theoretical computer science.

Review :
"This is a very interesting book on phase transitions and its connections to combinatorial optimization problems. The book is clearly written, up-to-date and well researched, including references to 23 of the authors' own research papers." (Mathematical Reviews, Issue 2009b) "This new book is a concise, comprehensive introduction to the topic of statistical physics of combinatorial optimization, bringing together theoretical concepts and algorithms from computer science with analytical methods from physics." (Metall) "A well-balanced, concise yet comprehensive introduction, combining statistical physics and combinatorial optimization." (Zeitschrift fur Kristallographie)