Combinatorial Optimization - Structures and Algorithms

Fall 2011, TuTh 4:35-5:55, CCB 102

The course covers fundamental topics in combinatorial optimization, such as connectivity, orientation, matching, packing and covering problems. The main focus is on min-max theorems and polynomial time algorithms for finding the exact optimal solution. The main purpose of the course to exploit the underlying deep combinatorial structures, and to understand the force of general methods as sub- and supermodular optimization uncrossing, and polyhedral methods.

Prerequisites are basic combinatorial optimization knowledge (shortest paths, spanning trees, bipartite matchings, maximum flows, etc.) and linear programming.

The basic textbook is Lex Schrijver's 3 volume Combinatorial Optimization, and the recent book Connections in Combinatorial Optimization by András Frank.

Some intended topics are:

László Végh