22921 Combinatorial Optimization

Credits: 4 graduate credits in Computer Science

Prerequisite: Admission to the graduate program in Computer Science 1

The course is based on chapters 1-5 and 7 in Combinatorial Optimization, by W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver (John Wiley & Sons, 1998).

The course is a natural continuation of the course, Algorithms (20417). It deals with algorithm design for important fundamental problems such as Maximum Matching in general graphs, the Minimum-Cost Flow problem, the Traveling Salesperson problem, and others. Also discussed are general techniques for algorithm design for optimization problems (techniques that are applicable to a broad family of problems).

Topics: Minimum cuts in undirected graphs; Minimum-Cost Flow problems; Algorithms for general matching problems; the Traveling Salesperson problem.

---

1Students who have not fulfilled this requirement may, under certain circumstances, enroll in this course.