## 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.
*