Details

Autor(en) / Beteiligte

• Hartmann, Alexander K
• Weigt, Martin

Titel

Phase transitions in combinatorial optimization problems : basics, algorithms and statistical mechanics [electronic resource]

Link zum Volltext

• Wiley Online Library - AutoHoldings Books

Beschreibungen/Notizen

• Description based upon print version of record.
• Includes bibliographical references and index.
• Phase Transitions in Combinatorial Optimization Problems Basics, Algorithms and Statistical Mechanics; 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.1.1 The bridges of Königsberg and Eulerian graphs; 3.1.2 Hamiltonian graphs; 3.1.3 Minimum spanning trees
• 3.1.4 Edge covers and vertex covers3.1.5 The graph coloring problem; 3.1.6 Matchings; 3.2 Basic graph algorithms; 3.2.1 Depth-first and breadth-first search; 3.2.2 Strongly connected component; 3.2.3 Minimum spanning tree; 3.3 Random graphs; 3.3.1 Two ensembles; 3.3.2 Evolution of graphs; 3.3.3 Finite-connectivity graphs: The case p = c/N; 3.3.4 The phase transition: Emergence of a giant component; 3.3.5 The emergence of a giant q-core; 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-completeness4.8 NP-complete problems; 4.8.1 Proving NP-completeness; 4.8.2 3-SAT; 4.8.3 Vertex cover; 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.2.1 The probability distribution for microscopic configurations; 5.2.2 Statistical meaning of the partition function; 5.2.3 Thermodynamic limit; 5.3 The Curie-Weiss model of a ferromagnet; 5.4 The Ising model on a random graph; 5.4.1 The model; 5.4.2 Some expectations; 5.4.3 The replica approach
• 5.4.4 The Bethe-Peierls approachBibliography; 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.6.1 The hard-core lattice gas; 6.6.2 Markov chains; 6.6.3 Monte Carlo for hard-core gases; 6.6.4 Parallel tempering; 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 approach7.4.1 The replicated partition function; 7.4.2 Replica-symmetric solution; 7.4.3 Beyond replica symmetry; Bibliography; 8 The dynamics of vertex-cover algorithms; 8.1 The typical-case solution time of a complete algorithm; 8.1.1 The algorithm; 8.1.2 Some numerical observations; 8.1.3 The first descent into the tree; 8.1.4 The backtracking time; 8.1.5 The dynamical phase diagram of branch-and-bound algorithms; 8.2 The dynamics of generalized leaf-removal algorithms; 8.2.1 The algorithm; 8.2.2 Rate equations for the degree distribution; 8.2.3 Gazmuri's algorithm
• 8.2.4 Generalized leaf removal
• 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 necess
• English