Mathematics 697CM - ST-Combinatorial Optimization

In this course, we will consider maximization and minimization problems in graphs and networks. We will cover a broad range of topics such as matchings in bipartite graphs and in general graphs, assignment problem, polyhedral combinatorics, total unimodularity, matroids, matroid intersection, min arborescence, max flow;min cut, max cut, traveling salesman problem, stable sets and perfect graphs. One of our main tools will be integer programming, and we will also sometimes rely on semidefinite programming. Many of these problems come from real-world applications, so we will also sometimes discuss the algorithms necessary to solve them. This is a rigorous mathematical introduction to combinatorial optimization with proofs.

Open to Graduate students only. Note: Pre-requisites for this course are:
Math 235 or equivalent
Math 455 or Math 513/CS 575 or equivalent