KTH /
Engineering Science
/
Mathematics
/
Optimization and Systems Theory
SF3846 Combinatorial optimization, 7.5hp
This course is primarily intended for graduate students in optimization
and systems theory, or other graduate students with a good background in
optimization.
Summary of contents
Study of 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.
Prerequisites
Suitable prerequisites is the course Applied linear optimization
(SF2812) or similar knowledge. Knowledge similar to the course
Integer programming - practical algorithms (SF3860) is also
of use, as well as knowledge of Matlab.
Textbook
C. H. Papadimitriou and K. Steiglitz.
Combinatorial Optimization: Algorithms and Complexity. Dover
Publications, Inc., 1998; ISBN 0-486-40258-4 (paperback). (May for
example be purchased
from Amazon, Adlibris or Bokus.)
Preliminary schedule
The course will be taught in the form of 12 lectures of 90 minutes
each. The first lecture will be given on Tuesday January 18, 2011, and
the remaining lectures will be given Tuesdays 8.15-10.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 18.)
Schedule for remaining lectures will be determined at the first lecture.
| Lecture 0 | | Introduction |
| Lecture 1 | Ch 5 | The primal-dual algorithm |
| | Ch 6 | Primal-dual algorithms for max-flow and
shortest path: Ford-Fulkerson and Dijkstra |
| | Ch 7 | Primal-dual algorithms for min-cost flow |
| Lecture 2 | Ch 8 | Algorithms and complexity |
| Lecture 3 | Ch 9 | Efficient algorithms for the max-flow problem |
| Lecture 4 | Ch 10 | Algorithms for matching |
| Lecture 5 | Ch 11 | Weighted matching |
| Lecture 6 | Ch 12 | Spanning trees and matroids |
| Lecture 7 | Ch 15 | NP-complete problems |
| Lecture 8 | Ch 16 | More about NP-completeness |
| Lecture 9 | Ch 17 | Approximation algorithms |
| Lecture 10 | Ch 18 | Branch-and-bound and dynamic programming |
| Lecture 11 | Ch 19 | Local search |
| Lecture 12 | | Selected heuristic algorithms |
Examination
The examination is by five sets of homework assignments and an oral final exam.
Examiner
Anders Forsgren, room 3703,
Lindstedtsvägen 25, tel. 790 71 27. E-mail: andersf@kth.se.
|
