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

3527404732......Page 4
Contents......Page 8
Preface......Page 12
1 Introduction......Page 16
1.1 Two examples of combinatorial optimization......Page 17
1.2 Why study combinatorial optimization using statistical physics?......Page 21
1.3 Textbooks......Page 25
Bibliography......Page 26
2.1 Pidgin Algol......Page 28
2.2 Iteration and recursion......Page 32
2.3 Divide-and-conquer......Page 33
2.4 Dynamic programming......Page 35
2.5 Backtracking......Page 37
Bibliography......Page 39
3.1.1 The bridges of Königsberg and Eulerian graphs......Page 40
3.1.2 Hamiltonian graphs......Page 44
3.1.3 Minimum spanning trees......Page 45
3.1.4 Edge covers and vertex covers......Page 47
3.1.5 The graph coloring problem......Page 48
3.1.6 Matchings......Page 51
3.2 Basic graph algorithms......Page 52
3.2.1 Depth-first and breadth-first search......Page 53
3.2.2 Strongly connected component......Page 60
3.2.3 Minimum spanning tree......Page 63
3.3.1 Two ensembles......Page 64
3.3.2 Evolution of graphs......Page 65
3.3.3 Finite-connectivity graphs: The case p = c/N......Page 66
3.3.4 The phase transition: Emergence of a giant component......Page 70
3.3.5 The emergence of a giant q-core......Page 73
Bibliography......Page 81
4 Introduction to complexity theory......Page 82
4.1 Turing machines......Page 83
4.2 Church’s thesis......Page 87
4.3 Languages......Page 89
4.4 The halting problem......Page 91
4.5 Class P......Page 93
4.6 Class NP......Page 95
4.7 Definition of NP-completeness......Page 98
4.8.2 3-SAT......Page 107
4.8.3 Vertex cover......Page 108
4.9 Worst-case vs. typical-case complexity......Page 111
Bibliography......Page 112
5.1 Phase transitions......Page 114
5.2.1 The probability distribution for microscopic configurations......Page 117
5.2.2 Statistical meaning of the partition function......Page 118
5.3 The Curie–Weiss model of a ferromagnet......Page 119
5.4.2 Some expectations......Page 125
5.4.3 The replica approach......Page 126
5.4.4 The Bethe–Peierls approach......Page 137
Bibliography......Page 143
6.1 Definitions......Page 144
6.2 Heuristic algorithms......Page 146
6.3 Branch-and-bound algorithm......Page 150
6.4 Results: Covering random graphs......Page 156
6.5 The leaf-removal algorithm......Page 162
6.6 Monte Carlo simulations......Page 165
6.6.1 The hard-core lattice gas......Page 166
6.6.2 Markov chains......Page 167
6.6.3 Monte Carlo for hard-core gases......Page 170
6.6.4 Parallel tempering......Page 173
6.7 Backbone......Page 175
6.8 Clustering of minimum vertex covers......Page 179
Bibliography......Page 182
7.1 Introduction......Page 186
7.2 The first-moment bound......Page 187
7.3 The hard-core lattice gas......Page 188
7.4 Replica approach......Page 189
7.4.1 The replicated partition function......Page 190
7.4.2 Replica-symmetric solution......Page 192
7.4.3 Beyond replica symmetry......Page 196
Bibliography......Page 197
8 The dynamics of vertex-cover algorithms......Page 198
8.1.1 The algorithm......Page 199
8.1.2 Some numerical observations......Page 201
8.1.3 The first descent into the tree......Page 202
8.1.4 The backtracking time......Page 204
8.1.5 The dynamical phase diagram of branch-and-bound algorithms......Page 206
8.2 The dynamics of generalized leaf-removal algorithms......Page 208
8.2.1 The algorithm......Page 209
8.2.2 Rate equations for the degree distribution......Page 210
8.2.3 Gazmuri’s algorithm......Page 213
8.2.4 Generalized leaf removal......Page 214
8.3 Random restart algorithms......Page 219
Bibliography......Page 225
9 Towards new, statistical-mechanics motivated algorithms......Page 226
9.1 The cavity graph......Page 227
9.2 Warning propagation......Page 229
9.2.1 Back to the replica results......Page 234
9.3 Belief propagation......Page 236
9.4 Survey propagation......Page 239
9.5 Numerical experiments on random graphs......Page 243
Bibliography......Page 245
10 The satisfiability problem......Page 246
10.1 SAT algorithms......Page 247
10.1.1 2-SAT algorithms......Page 248
10.1.2 Complete algorithms for K-SAT......Page 253
10.1.3 Stochastic algorithms......Page 259
10.2 Phase transitions in random K-SAT......Page 266
10.2.1 Numerical results......Page 267
10.2.2 Rigorous mathematical results......Page 268
10.2.3 Statistical-mechanics results......Page 271
10.3 Typical-case dynamics of Random WalkSAT......Page 273
10.3.2 An analytical approximation scheme for random K-SAT......Page 274
10.4.1 Factor graphs and cavities......Page 283
10.4.2 Warning propagation......Page 285
10.4.3 Survey propagation......Page 288
Bibliography......Page 292
11 Optimization problems in physics......Page 296
11.1.1 Simulated annealing......Page 298
11.1.2 Cluster algorithms......Page 300
11.1.3 Biased sampling......Page 304
11.2 Hysteric optimization......Page 306
11.3 Genetic algorithms......Page 310
11.4 Shortest paths and polymers in random media......Page 315
11.5 Maximum flows and random-field systems......Page 319
11.6 Submodular functions and free energy of Potts model......Page 327
11.7 Matchings and spin glasses......Page 332
Bibliography......Page 340
Index......Page 348