Overview
The lecture will cover optimization problems in physical systems with
an emphasis on optimization algorithms. Some combinatorial as well
as typical optimization problems (such as k-SAT, traveling salesman,
number partitioning, ...) will also be discussed. Furthermore, some
topics such as complexity theory as well as finite-size scaling will
be reviewed. Most of the examples will be based on physics spin models
(e.g., Ising model).
|
Lecture Notes
- 02/10: General introductory concepts,
complexity theory.
- 09/10: Spin glasses as algorithm benchmarks, Monte Carlo methods (simulated annealing, parallel tempering)
- 16/10: Genetic algorithms, hysteretic
optimization, extremal optimization
- 30/10: Patchwork dynamics, quantum annealing, SAT/UNSAT phase transition
- 06/11: Introduction to graphs, simple
algorithms and optimization problems
- 13/11: Random graphs, phase transitions in
the vertex cover problem
- 27/11: Maximum-flow methods
- 04/12: Dynamics in the cov/uncov
transition, methods to study spin glasses, genetic cluster exact
approximation
- 11/12: Probing low-probability tails,
the number partitioning problem
- 18/12: Matchings
Complete lecture (24 Mb)
If you would like to access the lectures
notes (pdf) please send me an email to katzgraber@phys.ethz.ch
and you might receive the username and password. Students can find
the username and password on the first handout.
|
Recommended books
- Optimization Algorithms in Physics, A. K. Hartmann and H.
Rieger (Wiley-VCH).
- New Optimization Algorithms in Physics, A. K. Hartmann and H.
Rieger (Wiley-VCH).
- Algorithms and Computations, W. Krauth (Oxford University Press).
- Phase Transitions in Combinatorial Optimization Problems, A. K.
Hartmann and M. Weigt (Wiley-VCH).
- Quantum Annealing and Related Optimization Methods, A. Das and B. K.
Chakrabarti (Springer).
|