MIT Department of Electrical Engineering & Computer Science

EECS Spring 2000 Catalogue Supplement

6.891 Approximation Algorithms (H)

F 1-4, 31-161
Dr. David Williamson, IBM TJ Watson Research Center
Prerequisite: 6.045J and 6.046J
3-0-9

This course will cover techniques in the design and analysis of efficient algorithms for the near-optimal solution of NP-hard problems in combinatorial optimization. Techniques covered will include: Dynamic programming and data rounding: Knapsack, scheduling, and bin packing. Randomization: maximum satisfiability. Semidefinite methods: maximum cuts, quadratic programming, and graph coloring. Metric methods: minimum multicuts, balanced cuts. Primal-dual method: feedback vertex set, generalized Steiner tree, facility location. Advanced applications of these techniques will be covered as time permits, including the Arora/Mitchell PTAS for Euclidean problems, Jain's rounding scheme for the survivable network design problem, and others.