CS 538: Combinatorial Optimization

Objectives

• The course will introduce techniques and tools for combinatorial optimization problem such as maximum weight graph matching, with rigorous analysis of polynomial-time algorithms.
• At the end of the course, students should be able to model real-time problems (such as optimization of computer networks) and, if possible, reduce the problem to one of the studied combinatorial optimization problem.

Prerequisites

CS 430 and a linear algebra course.

Syllabus

• Introductory concepts - convexity, linear programs
• Modeling and Integer Programming
• Linear programming- geometry of LP's, Simplex Method, Duality, Complementary slackness
• Polynomial-time algorithm(s) for Linear Programming
• Solving maximum flows, minimum-cost flows
• Matching and weighted matching in bipartite and general graphs
• Matroids (time permitting)
• Approximation Algorithms: Set Cover, Traveling Salesman

Edited March 2006 (html, css checks)