[an error occurred while processing this directive]


Kungl Tekniska högskolan / Optimization and Systems Theory /

[an error occurred while processing this directive]This is a printer-friendly version of https://math.kth.se/optsyst/forskning/forskarutbildning/SF3846/info.html

« [an error occurred while processing this directive]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 held on Tuesday August 29, 2017.

Subsequent lectures are held on Tuesdays, 9.15-11.00 in room F11, Lindstedtsvägen 22.

Lecture 1 Tu Aug 29 8-10   Introduction
Lecture 2 Tu Sep 5 9-11 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 3 Tu Sep 12 9-11 Ch 8 Algorithms and complexity
Lecture 4 Tu Sep 19 9-11 Ch 9 Efficient algorithms for the max-flow problem
Lecture 5 Tu Sep 26 9-11 Ch 10 Algorithms for matching
Lecture 6 Tu Oct 3 9-11 Ch 11 Weighted matching
Lecture 7 Tu Oct 10 9-11 Ch 12 Spanning trees and matroids
Lecture 8 Tu Oct 17 9-11 Ch 15 NP-complete problems
Lecture 9 Mo Oct 23 8-10 Ch 16 More about NP-completeness
Lecture 10 Tu Oct 31 10-12 Ch 17 Approximation algorithms
Lecture 11 Tu Nov 7 9-11 Ch 18 Branch-and-bound and dynamic programming
Lecture 12 Tu Nov 14 9-11 Ch 19 Local search and selected heuristic algorithms

Examination

The examination is by five sets of homework assignments and an oral final exam.

Examiner

Anders Forsgren, room 3533, Lindstedtsvägen 25, tel. 790 71 27. E-mail: andersf@kth.se.

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