# This is an archived page and may be obsolete; the current pages are at http://www.iit.edu/csl/cs

# 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)