| | Contents | |
| | | |
| |
| | Preface | IX |
| 1 | Introduction | 1 |
| 1.1 | Two examples of combinatorial optimization | 2 |
| 1.2 | Why study combinatorial optimization using statistical physics? | 6 |
| 1.3 | Textbooks | 10 |
| | Bibliography | 11 |
| 2 | Algorithms | 13 |
| 2.1 | Pidgin Algol | 13 |
| 2.2 | Iteration and recursion | 17 |
| 2.3 | Divide and conquer | 18 |
| 2.4 | Dynamic programming | 20 |
| 2.5 | Backtracking | 22 |
| | Bibliography | 24 |
| 3 | Introduction to graphs | 25 |
| 3.1 | Basic concepts and graph problems | 25 |
| 3.1.1 | The bridges of Königsberg and Eulerian graphs | 25 |
| 3.1.2 | Hamiltonian graphs | 29 |
| 3.1.3 | Minimum spanning trees | 30 |
| 3.1.4 | Edge covers and vertex covers | 32 |
| 3.1.5 | The graph coloring problem | 33 |
| 3.1.6 | Matchings | 36 |
| 3.2 | Basic graph algorithms | 37 |
| 3.2.1 | Depth-first and breadth-first search | 38 |
| 3.2.2 | Strongly connected component | 45 |
| 3.2.3 | Minimum spanning tree | 48 |
| 3.3 | Random graphs | 49 |
| 3.3.1 | Two ensembles | 49 |
| 3.3.2 | Evolution of graphs | 50 |
| 3.3.3 | Finiteconnectivity graphs: The case p = c/N | 51 |
| 3.3.4 | The phase transition: Emergence of a giant component | 55 |
| 3.3.5 | The emergence of a giant q-core | 58 |
| | Bibliography | 66 |
| 4 | Introduction to complexity theory | 67 |
| 4.1 | Turing machines | 68 |
| 4.2 | Church's thesis | 72 |
| 4.3 | Languages | 74 |
| 4.4 | The halting problem | 76 |
| 4.5 | Class P | 78 |
| 4.6 | Class NP | 80 |
| 4.7 | Definition of NP-completeness | 83 |
| 4.8 | NP-complete problems | 92 |
| 4.8.1 | Proving NP-completeness | 92 |
| 4.8.2 | 3-SAT | 92 |
| 4.8.3 | Vertex cover | 93 |
| 4.9 | Worst-case vs. typical-case complexity | 96 |
| | Bibliography | 97 |
| 5 | Statistical mechanics of the Ising model | 99 |
| 5.1 | Phase transitions | 99 |
| 5.2 | Some general notes on statistical mechanics | 102 |
| 5.2.1 | The probability distribution for microscopic configurations | 102 |
| 5.2.2 | Statistical meaning of the partition function | 103 |
| 5.2.3 | Thermodynamic limit | 104 |
| 5.3 | The Curie-Weiss model of a ferromagnet | 104 |
| 5.4 | The Ising model on a random graph | 110 |
| 5.4.1 | The model | 110 |
| 5.4.2 | Some expectations | 110 |
| 5.4.3 | The replica approach | 111 |
| 5.4.4 | The Bethe--Peierls approach | 122 |
| | Bibliography | 128 |
| 6 | Algorithms and numerical results for vertex covers | 129 |
| 6.1 | Definitions | 129 |
| 6.2 | Heuristic algorithms | 131 |
| 6.3 | Branch-and-bound algorithm | 135 |
| 6.4 | Results: Covering random graphs | 141 |
| 6.5 | The leaf-removal algorithm | 147 |
| 6.6 | Monte Carlo simulations | 150 |
| 6.6.1 | The hard-core lattice gas | 151 |
| 6.6.2 | Markov chains | 152 |
| 6.6.3 | Monte Carlo for hardcore gases | 155 |
| 6.6.4 | Parallel tempering | 158 |
| 6.7 | Backbone | 160 |
| 6.8 | Clustering of minimum vertex covers | 164 |
| | Bibliography | 167 |
| 7 | Statistical mechanics of vertex covers on a random graph | 171 |
| 7.1 | Introduction | 171 |
| 7.2 | The first-moment bound | 172 |
| 7.3 | The hard-core lattice gas | 173 |
| 7.4 | Replica approach | 174 |
| 7.4.1 | The replicated partition function | 175 |
| 7.4.2 | Replica-symmetric solution | 177 |
| 7.4.3 | Beyond replica symmetry | 181 |
| | Bibliography | 182 |
| 8 | The dynamics of vertexcover algorithms | 183 |
| 8.1 | The typical-case solution time of a complete algorithm | 184 |
| 8.1.1 | The algorithm | 184 |
| 8.1.2 | Some numerical observations | 186 |
| 8.1.3 | The first descent into the tree | 187 |
| 8.1.4 | The backtracking time | 189 |
| 8.1.5 | The dynamical phase diagram of branch-and-bound algorithms | 191 |
| 8.2 | The dynamics of generalized leaf-removal algorithms | 193 |
| 8.2.1 | The algorithm | 194 |
| 8.2.2 | Rate equations for the degree distribution | 195 |
| 8.2.3 | Gazmuri's algorithm | 198 |
| 8.2.4 | Generalized leaf removal | 199 |
| 8.3 | Random restart algorithms | 204 |
| | Bibliography | 210 |
| 9 | Towards new, statistical-mechanics motivated algorithms | 211 |
| 9.1 | The cavity graph | 212 |
| 9.2 | Warning propagation | 214 |
| 9.2.1 | Back to the replica results | 219 |
| 9.3 | Belief propagation | 221 |
| 9.4 | Survey propagation | 224 |
| 9.5 | Numerical experiments on random graphs | 228 |
| | Bibliography | 230 |
| 10 | The satisfiability problem | 231 |
| 10.1 | SAT algorithms | 232 |
| 10.1.1 | 2-SAT algorithms | 233 |
| 10.1.2 | Complete algorithms for K-SAT | 238 |
| 10.1.3 | Stochastic algorithms | 244 |
| 10.2 | Phase transitions in random K-SAT | 251 |
| 10.2.1 | Numerical results | 252 |
| 10.2.2 | Rigorous mathematical results | 253 |
| 10.2.3 | Statistical-mechanics results | 256 |
| 10.3 | Typical-case dynamics of RandomWalkSAT | 258 |
| 10.3.1 | Numerical results | 259 |
| 10.3.2 | An analytical approximation scheme for random K-SAT | 259 |
| 10.4 | Message-passing algorithms for SAT | 268 |
| 10.4.1 | Factor graphs and cavities | 268 |
| 10.4.2 | Warning propagation | 270 |
| 10.4.3 | Survey propagation | 273 |
| | Bibliography | 277 |
| 11 | Optimization problems in physics | 281 |
| 11.1 | Monte Carlo optimization | 283 |
| 11.1.1 | Simulated annealing | 283 |
| 11.1.2 | Cluster algorithms | 285 |
| 11.1.3 | Biased sampling | 289 |
| 11.2 | Hysteric optimization | 291 |
| 11.3 | Genetic algorithms | 295 |
| 11.4 | Shortest paths and polymers in random media | 300 |
| 11.5 | Maximum flows and random-field systems | 304 |
| 11.6 | Submodular functions and free energy of Potts model | 312 |
| 11.7 | Matchings and spin glasses | 317 |
| | Bibliography | 325 |
| | Index | 333 |
