Phase transitions in combinatorial optimization problems : basics, algorithms and statistical mechanics

>> Google Books

所蔵情報QRコード

Phase transitions in combinatorial optimization problems : basics, algorithms and statistical mechanics / Alexander K. Hartmann and Martin Weigt

資料種別:

図書

出版情報:

Weinheim, [Bergstr.] : WILEY-VCH, c2005

形態:

xi, 348 p. ; 25 cm

著者名:

ISBN:

9783527404735 [3527404732]

書誌ID:

BA74252014

子書誌情報

フルテキスト

所蔵情報

他の版・巻

書誌詳細

注記:

Includes bibliographical references and index

主題:

統計力学

言語:

英語

目次情報:

Preface

Introduction / 1：

Two examples of combinatorial optimization / 1.1：

Why study combinatorial optimization using statistical physics? / 1.2：

Textbooks / 1.3：

Bibliography

Algorithms / 2：

Pidgin Algol / 2.1：

Iteration and recursion / 2.2：

Divide-and-conquer / 2.3：

Dynamic programming / 2.4：

Backtracking / 2.5：

Introduction to graphs / 3：

Basic concepts and graph problems / 3.1：

Basic graph algorithms / 3.2：

Random graphs / 3.3：

Introduction to complexity theory / 4：

Turing machines / 4.1：

Church's thesis / 4.2：

Languages / 4.3：

The halting problem / 4.4：

Class P / 4.5：

Class NP / 4.6：

Definition of NP-completeness / 4.7：

NP-complete problems / 4.8：

Worst-case vs . typical-case complexity / 4.9：

Statistical mechanics of the Ising model / 5：

Phase transitions / 5.1：

Some general notes on statistical mechanics / 5.2：

The Curie-Weiss model of a ferromagnet / 5.3：

The Ising model on a random graph / 5.4：

Algorithms and numerical results for vertex covers / 6：

Definitions / 6.1：

Heuristic algorithms / 6.2：

Branch-and-bound algorithm / 6.3：

Results: Covering random graphs / 6.4：

The leaf-removal algorithm / 6.5：

Monte Carlo simulations / 6.6：

Backbone / 6.7：

Clustering of minimum vertex covers / 6.8：

Statistical mechanics of vertex covers on a random graph / 7：

The first-moment bound / 7.1：

The hard-core lattice gas / 7.3：

Replica approach / 7.4：

The dynamics of vertex-cover algorithms / 8：

The typical-case solution time of a complete algorithm / 8.1：

The dynamics of generalized leaf-removal algorithms / 8.2：

Random restart algorithms / 8.3：

Towards new, statistical-mechanics motivated algorithms / 9：

The cavity graph / 9.1：

Warning propagation / 9.2：

Belief propagation / 9.3：

Survey propagation / 9.4：

Numerical experiments on random graphs / 9.5：

The satisfiability problem / 10：

SAT algorithms / 10.1：

Phase transitions in random K-SAT / 10.2：

Typical-case dynamics of RandomWalkSAT / 10.3：

Message-passing algorithms for SAT / 10.4：

Optimization problems in physics / 11：

Monte Carlo optimization / 11.1：

Hysteric optimization / 11.2：

Genetic algorithms / 11.3：

Shortest paths and polymers in random media / 11.4：

Maximum flows and random-field systems / 11.5：

Submodular functions and free energy of Potts model / 11.6：

Matchings and spin glasses / 11.7：

Index

Preface

Introduction / 1：

Two examples of combinatorial optimization / 1.1：

Why study combinatorial optimization using statistical physics? / 1.2：

Textbooks / 1.3：

Bibliography

続きを見る

東工大ブックレビュー

類似資料:

1 図書 Optimization algorithms in physics Hartmann, Alexander K., Rieger, Heiko Wiley-VCH	7 図書 Statistical mechanics and scientific explanation : determinism, indeterminism and laws of nature (: hardcover) Allori, Valia World Scientific
2 図書 Absorbing phase transitions (: hbk.) Henkel, M. (Malte), 1960-, Hinrichsen, Haye, Lübeck, Sven Springer, In association with Canopus Academic Publishing Limited	8 電子ブック Gems of Combinatorial Optimization and Graph Algorithms Schulz, Andreas S., Skutella, Martin, Stiller, Sebastian, Wagner, Dorothea SpringerLink Books - AutoHoldings, Springer International Publishing
3 図書 Statistical mechanics of phase transitions (: pbk) Yeomans, J. M Clarendon Press, Oxford University Press	9 図書熱・統計力学 = Thermodynamics and statistical mechanics 為近, 和彦森北出版
4 図書 Elements of statistical mechanics Haar, D. ter, 1919- Rinehart	10 図書 Potts models and related problems in statistical mechanics Martin, Paul P. (Paul Purdon) World Scientific
5 図書 Entropy, large deviations, and statistical mechanics (: us ; : gw) Ellis, Richard S. (Richard Steven), 1947- Springer-Verlag	11 電子ブック Theory of Phase Transitions in Polypeptides and Proteins Yakubovich, Alexander V. SpringerLink Books - AutoHoldings, Springer Berlin Heidelberg
6 図書 Microstates, Entropy and Quanta : An Introduction to Statistical Mechanics Koks, Don Springer	12 図書 Structural elements in particle physics and statistical mechanics NATO Advanced Summer Institute on Theoretical Physics, Honerkamp, J., Pohlmeyer, K., Römer, Hartmann, North Atlantic … Plenum Press