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.
The course will be taught in the form of 12 lectures of 90 minutes each. The first lecture will be given on Wednesday January 24, 2007, at 10.15-12.00, in Room 3721, Lindstedtsvägen 25. The preliminary schedule is given below, giving the relevant chapters from the textbook. (Lecture 0 will be given on January 24.)
|Lecture 1||5||The primal-dual algorithm|
|6||Primal-dual algorithms for max-flow and shortest path: Ford-Fulkerson and Dijkstra|
| ||7||Primal-dual algorithms for min-cost flow|
|Lecture 2||8||Algorithms and complexity|
|Lecture 3||9||Efficient algorithms for the max-flow problem|
|Lecture 4||10||Algorithms for matching|
|Lecture 5||11||Weighted matching|
|Lecture 6||12||Spanning trees and matroids|
|Lecture 7||15||NP-complete problems|
|Lecture 8||16||More about NP-completeness|
|Lecture 9||17||Approximation algorithms|
|Lecture 10||18||Branch-and-bound and dynamic programming|
|Lecture 11||19||Local search|
|Lecture 12||Selected heuristic algorithms|