Instructor: Dr. András FRANK or Dr. Tibor JORDÁN

Text:  classnotes, handouts and A. Schrijver, A course in Combinatorial Optimization (2009)

Prerequisite:

Topics:

• Polynomial algorithms, NP-problems, NP-complete problems. Reachability and cheapest (shortest) paths in digraphs, conservative weigthings and feasible potentials.
• Greedy algorithms, finding cheapest trees and cheapest arborescences.
• Bipartite matchings, stable matchings, degree-constrained orientation of graphs, chain and antichain decomposition of posets. Disjoint paths in graphs.
• Assignment problem: the Hungarian method, maximum flows.
• Non-bipartite matchings, T-joins.
• Elements of matroid theory with applications.
• Elements of linear programming, applications of totally unimodular matrices.