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 email
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).
|