Kungl Tekniska högskolan / Optimization and Systems Theory /

This is a printer-friendly version of (none)

« Back
 


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.

Optimization and Systems Theory, KTH
Anders Forsgren, andersf@kth.se