Course Websites

The course will cover a series of topics in combinatorial optimization. The emphasis will be on polyhedral theory, structural results and their applications to designing algorithms. Specific topics to be covered include: Matchings, b-matchings, T-joins, T-cuts, Arborescences, Branchings, Matroids, Matroid Intersection, Polymatroids, Submodular Functions, Directed Cuts, Multi-flows. Course Information: Same as CS 586. 4 graduate hours. No professional credit. Prerequisite: Familiarity with linear programs (IE 411 or equivalent), Algorithms (CS 374 or equivalent), and Graph Theory (Math 412 or equivalent).