Discrete Optimization is about the problem of finding a best solution among a (finite) set of feasible solutions. A well-known example is the traveling salesman problem, where we are asked to find the shortest tour in a graph visiting every node exactly once. Throughout the course we will consider several fundamental problems from the area and develop efficient algorithms to solve them.
We plan to cover the following topics:
- Shortest Path Algorithms
- Minimum Spanning Trees & Matroids
- Maximum Flows & Minimum Cuts
- Minimum Cost Flows
- Integer Linear Programming & Total Unimodularity
- Complexity Theory (P vs. NP)
- Approximation Algorithms
- Inapproximability & Approximation Schemes
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 very good basis; it actually covers more background material than we will need in the course.
- Docent: Bodo Manthey