Combinatorial Optimization credit:

4 Hours

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. Same as CS 586 . Prerequisite: Familiarity with linear programs ( IE 411 or equivalent), Algorithms ( CS 374 or equivalent), and Graph Theory ( MATH 412 or equivalent).