Discrete Optimization (LNMB/3TU)

Credits	6 credit points
Instructors	Kern, W. (Universiteit Twente)
E-mail	w.kern@math.utwente.nl
Aim	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.
Description	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 7. Matching 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)
Organization	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 "x.qiu@utwente.nl").
Examination	by written exam. To pass, students are required to yield at least 5.5 for both exercises and written exam.
Literature	the reader by Guido Schaefer (pointing at further references) can be downloaded from WWW: http://wwwhome.math.utwente.nl/~kernw/.
Prerequisites	Linear Programming and some basic graph theory.

Last changed: 22-05-2013 16:30