Matroids and submodular optimization

A matroid is a very useful notion in combinatorial optimization. It generalizes the greedy property observed in some optimization problems, like Kruskal's algorithm for finding a minimum cost spanning tree. It is general enough to capture many situations, but is special enough to have interesting properties. It is successfully applied in the design of approximation algorithms, too. Matroids are ``around us'': cycleless subsets of edges of a graph form a graphic matroid, linearly independent subsets of a set of vectors form a linear matroid, the subsets of nodes of a graph that can be covered by a matching form a matching matroid, etc.

Course advertisment (download and watch locally for best performance)

The course will give an introduction to matroid theory, submodularity and their applications in combinatorial optimization. We build on basic knowledge of linear programming and graph theory. As a course book we will use the recent book by András Frank titled ``Connections in Combinatoial Optimization''.

- An introduction to submodularity (definitions, proof techniques, applications)

- Matroid axioms (independence, rank, circiuts, bases)

- Matroid algorithms and polyhedra

- Matroid constructions (basic constructions, matroids from matchings and paths, matroids from matroids and from submodular functions)

- Applications of matroids (root sets of arc-disjoint arborescences, source sets in digraphs, count matroids)

- Matroid intersection, matroid union (and their weighted case)

- Applications of matroid intersection and union (maximum weight matchings, k-edge-connected orientations, rooted k-edge-connected subdigraphs, packing trees and covering with trees)

Lecture notes

Topics for the exam