Instructor: Anders Forsgren.
The course covers some fundamental combinatorial optimization problems: algorithms, complexity and applications. Algorithms: Maxflow-mincut-theorem. Primal-dual method for linear programming, with applications to network flows. Efficient algorithms for maxflow problems. Matching. Minimal spanning trees. Matroids. Complexity: NP-completeness, foundations and relevant examples. Applications: Heuristic methods for some interesting problem classes.
T