Combinatorial Optimization COP
Instructor: Dr. András FRANK or Dr. Tibor JORDÁN
Text: classnotes, handouts and A. Schrijver, A course in Combinatorial Optimization (2009)
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.