Motivation:
A great part of computerized problem solving made by industry may be formulated as optimization and searching problems over a very large space of possible solutions. Examples go from software for the solution of logistic problems such as transport of goods, via web-caching to software to beat Kasparov at chess.
Many, but not all, of these optimization and searching problems will be difficult in the sense that there are no well-known efficient algorithms to solve them in practice. For these problems there are a number of techniques for finding satisfactory, non-optimal solutions.
Content:
Searching problems with efficient solutions:
Max-flow algorithms, linear programming etc.
Handling of difficult search problems (NP-hard):
- Speeding up exhaustive search: - e.g. Branch and bound, Davis-Putman procedure and (a,b)-game tree search.
- Local search - e.g. taboo search, simulated annealing and genetic algorithms.
- Rigorous approximation, in particular randomized techniques, such as randomized rounding.
Lecturers:
Peter Bro Miltersen and Sven Skyum
Prerequisites
Algorithmics
Course Language
Danish or English
Credits
2 points/10 ECTS credits