Combinatorial Optimization



  • 2018 Spring/Summer (Jan - May)

Brief description: We will cover efficient algorithms for optimization and analysis of combinatorial objects, including graphs, matroids, polyhedra, and derived structures. This is intended to be a higher-level algorithms course. Topics to be covered include matchings, flows and cuts, matroids, matroid intersection, related polyhedra, and linear programming techniques.

References: primarily lecture notes from the course taught by Michel Goemans. The CLRS book is a reasonable initial reference. Other relevant books include "Combinatorial Optimization: Algorithms and Complexity" by Papadimitriou and Steiglitz, and "Combinatorial Optimization" by Cook et al.

Requirements: mathematical aptitude, including writing concise mathematical proofs. A previous course in discrete math, and a course in algorithms, are recommended but not required. You should be prepared to put in extra effort if you have not taken these courses.