Discrete Optimization - 6EC

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:

  • Shortest Path Algorithms,
  • Spanning Trees, Matroids and the Greedy Algorithm,
  • Maximum Flows & Minimum Cuts,
  • Minimum Cost Flows,
  • Matchings in Graphs,
  • Integer Linear Programming & Total Unimodularity,
  • Basic Computational Complexity (P vs. NP),
  • Approximation Algorithms,
  • Inapproximability & Approximation Schemes.

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.

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 an average grade of at least 5.5, both in the homework assignments and the exam.

Homework: 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.5.

Exam: You are allowed to bring five sheets of A4 paper to the exam. What is written on the paper (handwritten, printed, ...) does not matter. Books, more paper, or electronic devices of any kind are not allowed.