| | Contents | |
| | | |
| |
| 1 | Introduction to Optimization | 1 |
| | Bibliography | 6 |
| 2 | Complexity Theory | 9 |
| 2.1 | Algorithms | 9 |
| 2.2 | Time Complexity | 16 |
| 2.3 | NP Completeness | 19 |
| 2.4 | Programming Techniques | 26 |
| | Bibliography | 34 |
| 3 | Graphs | 37 |
| 3.1 | Graphs | 37 |
| 3.2 | Trees and Lists | 39 |
| 3.3 | Networks | 42 |
| 3.4 | Graph Representations | 44 |
| 3.5 | Basic Graph Algorithms | 48 |
| 3.6 | NP-Complete Graph Problems | 50 |
| | Bibliography | 52 |
| 4 | Simple Graph Algorithms | 53 |
| 4.1 | The Connectivity-percolation Problem | 53 |
| 4.1.1 | Hoshen-Kopelman Algorithm | 54 |
| 4.1.2 | Other Algorithms for Connectivity Percolation | 57 |
| 4.1.3 | General Search Algorithms | 57 |
| 4.2 | Shortest-path Algorithms | 61 |
| 4.2.1 | The Directed Polymer in a Random Medium | 62 |
| 4.2.2 | Dijkstra´s Algorithm | 63 |
| 4.2.3 | Label-correcting Algorithm | 67 |
| 4.3 | Minimum Spanning Tree | 68 |
| | Bibliography | 71 |
| 5 | Introduction to Statistical Physics | 73 |
| 5.1 | Basics of Statistical Physics | 73 |
| 5.2 | Phase Transitions | 78 |
| 5.3 | Percolation and Finite-size Scaling | 81 |
| 5.4 | Magnetic Transition | 84 |
| 5.5 | Disordered Systems | 87 |
| | Bibliography | 90 |
| 6 | Maximum-flow Methods | 91 |
| 6.1 | Random-field Systems and Diluted Antiferromagnets | 92 |
| 6.2 | Transformation to a Graph | 96 |
| 6.3 | Simple Maximum Flow Algorithms | 102 |
| 6.4 | Dinic´s Method and the Wave Algorithm | 107 |
| 6.5 | Calculating all Ground States | 115 |
| 6.6 | Results for the RFIM and the DAFF | 121 |
| | Bibliography | 125 |
| 7 | Minimum-cost Flows | 129 |
| 7.1 | Motivation | 129 |
| 7.2 | The Solution of the N-Line Problem | 133 |
| 7.3 | Convex Mincost-flow Problems in Physics | 136 |
| 7.4 | General Minimum-cost-flow Algorithms | 139 |
| 7.5 | Miscellaneous Results for Different Models | 147 |
| | Bibliography | 155 |
| 8 | Genetic Algorithms | 159 |
| 8.1 | The Basic Scheme | 159 |
| 8.2 | Finding the Minimum of a Function | 164 |
| 8.3 | Ground States of One-dimensional Quantum Systems | 172 |
| 8.4 | Orbital Parameters of Interacting Galaxies | 178 |
| | Bibliography | 183 |
| 9 | Approximation Methods for Spin Glasses | 185 |
| 9.1 | Spin Glasses | 185 |
| 9.1.1 | Experimental Results | 187 |
| 9.1.2 | Theoretical Approaches | 190 |
| 9.2 | Genetic Cluster-exact Approximation | 192 |
| 9.3 | Energy and Ground-state Statistics | 203 |
| 9.4 | Ballistic Search | 208 |
| 9.5 | Results | 219 |
| | Bibliography | 222 |
| 10 | Matchings | 227 |
| 10.1 | Matching and Spin Glasses | 227 |
| 10.2 | Definition of the General Matching Problem | 228 |
| 10.3 | Augmenting Paths | 230 |
| 10.4 | Matching Algorithms | 231 |
| 10.4.1 | Maximum-cardinality Matching on Bipartite Graphs | 231 |
| 10.4.2 | Minimum-weight Perfect Bipartite Matching | 235 |
| 10.4.3 | Cardinality Matching on General Graphs | 241 |
| 10.4.4 | Minimum-weight Perfect Matching on General Graphs | 242 |
| 10.5 | Ground-state Calculations in 2d | 250 |
| | Bibliography | 252 |
| 11 | Monte Carlo Methods | 255 |
| 11.1 | Stochastic Optimization: Simple Concepts | 255 |
| 11.2 | Simulated Annealing | 257 |
| 11.3 | Parallel Tempering | 260 |
| 11.4 | Prune-enriched Rosenbluth Method (PERM) | 262 |
| 11.5 | Protein Folding | 266 |
| | Bibliography | 270 |
| 12 | Branch-and-bound Methods | 273 |
| 12.1 | Vertex Covers | 274 |
| 12.2 | Numerical Methods | 277 |
| 12.3 | Results | 287 |
| | Bibliography | 291 |
| 13 | Practical Issues | 293 |
| 13.1 | Software-Engineering | 293 |
| 13.2 | Object-oriented Software Development | 300 |
| 13.3 | Programming Style | 306 |
| 13.4 | Programming Tools | 310 |
| 13.4.1 | Using Macros | 310 |
| 13.4.2 | Make Files | 314 |
| 13.4.3 | Scripts | 317 |
| 13.5 | Libraries | 319 |
| 13.5.1 | Numerical Recipes | 319 |
| 13.5.2 | LEDA | 321 |
| 13.5.3 | Creating your own Libraries | 323 |
| 13.6 | Random Numbers | 324 |
| 13.6.1 | Generating Random Numbers | 324 |
| 13.6.2 | Inversion Method | 327 |
| 13.6.3 | Rejection Method | 328 |
| 13.6.4 | The Gaussian Distribution | 330 |
| 13.7 | Tools for Testing | 331 |
| 13.7.1 | gdb | 332 |
| 13.7.2 | ddd | 334 |
| 13.7.3 | checkergcc | 334 |
| 13.8 | Evaluating Data | 338 |
| 13.8.1 | Data Plotting | 338 |
| 13.8.2 | Curve Fitting | 340 |
| 13.8.3 | Finite-size Scaling | 343 |
| 13.9 | Information Retrieval and Publishing | 347 |
| 13.9.1 | Searching for Literature | 347 |
| 13.9.2 | Preparing Publications | 349 |
| | Bibliography | 355 |
| | Index | 359 |
| | | |
