Combinatorial Optimization

Graduate

This course will provide a rigorous introduction to combinatorial optimization. The student will develop a solid understanding of the theory, algorithms and applications of these problems and their connections to integer programming, linear programming and complexity theory. Topics will include: formulation of combinatorial optimization problems, polytopes and polyhedra, elements of computational complexity theory, shortest paths, bipartite and non-bipartite matchings, max-flow min-cut theorem, multi- commodity flow problems, clique and coloring problems, perfect graphs, traveling salesman problem, spanning trees, matroids.