||6 credit points
||Kern, W. (Universiteit Twente)
Discrete - as opposed to continuous - optimization seeks to find optimal solutions among (essentially) finitely many feasible solutions. It includes Linear and Integer Programming, as well as many graph theoretical optimization problems. In addition, the course presents a short introduction to complexity theory and approximation.
The course is based on the reader composed (and used last year) by Guido Schaefer. There are 10 chapters:
1. Preliminaries (reviewing also some necessary prerequisites)
2. Min spanning trees
3. Matroids and the greedy algorithm
4. Shortest paths in graphs
5. Max flow
6. Min cost flow
8. Integrality of polyhedra (reproving some of the previous results in a different way)
9. Complexity theory (seeking to classify problems as "easy" or "hard")
10. Approximation algorithms (computing "approximately" optimal solutions for certain problems)
||After the first introductory 2 hour course we intend (just like last year) to have two 2 hour courses every second week (alternating with Continuous Opt).
There will be take home exercises to be worked out in groups of 2-3 students and handed in one week after (preferably by mail to "firstname.lastname@example.org").
||by written exam. To pass, students are required to yield at least 5.5 for both exercises and written exam.
||the reader by Guido Schaefer (pointing at further references) can be downloaded from WWW: http://wwwhome.math.utwente.nl/~kernw/.
Linear Programming and some basic graph theory.