Discrete Optimization - M1 - 6EC

Prerequisites

Basic knowledge of algorithms, linear algebra and graph theory at the bachelor level. The material in "Appendix VIII: Mathematical Background" in the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein constitutes a good basis; it actually covers more background material than we will need in the course.

Aim of the course

Discrete Optimization addresses structural and algorithmic questions for finding the "best" among a set of feasible solutions. Often, this set of feasible solutions is finite, such as the set of maximal matchings in a finite graph, the set of vertices of a polytope, etc. Only since around the 1960s, starting with groundbreaking work of Jack Edmonds, researchers started to realize that the quality of procedures to solve such problems should be measured in terms of the algebraic dependence of computation time on problems size. Discrete Optimization has since then evolved into a rich mathematical area that connects to many other areas in mathematics but also computer science. Throughout the course, we consider several fundamental problems from this area and develop efficient algorithms to solve them.

Specifically, we cover the following topics :

  • Spanning Trees, Matroids, and Shortest Path Algorithms (Lectures 1&2),
  • Algorithms for Maximum Flows, Flow Duality (Lectures 3&4),
  • Algorithms for Matchings and Matroid Intersection (Lectures 5&6),
  • Minimum Cost Flows (Lecture 7)
  • Crash Course Polyhedral Combinatorics (Lecture 8),
  • Basic Computational Complexity: P,NP, Reductions (Lecture 9),
  • Approximation Algorithms, Inapproximability & Approximation Schemes (Lectures 10-12).

Lecturers

Marc Uetz (UT)


Rules about Homework/Exam
The final grade of the course depends on two parts:

graded homework assignments (30%), and written exam (70%).

In order to pass the course you need to achieve a grade of at least 5.5, both in the homework assignments and the exam.

Homework: The homework is compulsory. The formula to determine your grade for the homework assignments is as follows: 9(#points)/(max #points) + 1, then rounded to the closest multiple of 0.1. Here, the worst of all 12 homework grades is taken out of the calculation.

Exam: The examination is a written exam. It will (most probably, hopefully) be on location in Utrecht. I would not mind to say it is open book yet this is difficult to organize, as most material is electronic and I do not want that you print tons of paper that get thrown away anyhow. So what you may bring to the exam is some handwritten notes (let us say max 4x A4, both sides).

Your exam grade is again 9(#points)/(max #points) + 1, rounded to the closest multiple of 0.1.

Re-Exam: The same rules as for the regular exam apply. The grade for homework assignments carries over to the re-examination; in other words, the final grade will be calculated in the same way.

Lecture notes / literature

Additional literature that is related to this course is:

  • T. Cormen, C. Leiserson, R. Rivest and C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001. (or any newer edition)

  • W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver: Combinatorial Optimization, Wiley, 1998.

  • B. Korte and J. Vygen: Combinatorial Optimization, Theory and Algorithms, 5th ed., Springer, 2011.

  • R.K. Ahuja, T.L. Magnanti J.B. Orlin: Network Flows, Prentice Hall, 1993.

  • V. Vazirani: Approximation Algorithms, Springer, 2001.

  • U. Faigle, W. Kern, G. Still: Algorithmic Principles of Mathematical Programming, Springer, 2002.

Courses with topics related to the Discrete Optimization course are e.g.:

PhD courses by the LNMB that might be interesting, too (note, these courses are offered in a bi-annual model, so every two years, and you may need to consult your programme if they would be considered eligible, as these course go w/o exams, only with homework)