Course topics

The course will cover most of the following topics:

• Maximum Flow: The Goldberg-Tarjan Push-Relabel max-flow algorithm
• Minimum cuts: Gomory-Hu tree cuts, global minimum cuts
• Min-Cost Flow: cancellation of negative cycle, capacity scaling, min cycle mean, overview of Goldberg-Tarjan algorithm
• Matchings in undirected graphs: Edmonds algorithm for the unweighted case.
• Coloring: greedy vertex coloring and edge coloring.
• Connectivity: Menger's Theorem.
• Linear Programming: Farkas' Lemma, duality, complementary slackness, Simplex algorithm.
• If time permits, some of these topics: PTAS for fractional covering/packing, online covering/packing, separator theorem for planar graphs.