next up previous contents
Next: Doctoral theses Up: Graduate courses Previous: 5B5850 Numerical Linear Programming,

5B5870 Combinatorial Optimization, 5 p

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



Anders Forsgren
2/21/2001