5B5870 Combinatorial optimization, 5p

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 (5B1815) or similar knowledge. Knowledge similar to the course Integer programming - practical algorithms (5B5860) 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) or Prentice-Hall, 1982; ISBN 0-13-152462-3 (hardbound, out of print).

Preliminary schedule

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 0   Introduction
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

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.
5B5870 Combinatorial optimization
by Anders Forsgren.