Introduction to approximation algorithms, where the goal is to find provably good approximation solutions for optimization problems that are hard to solve exactly. Over the last several years, a number of techniques have emerged for the design of approximation algorithms for a wide variety of problems. The goal of the course is to introduce students to these general algorithmic techniques. Mathematical programming relaxations are a very useful tool for the design of approximation algorithms. We will study approximation algorithms derived from linear programming relaxations via randomized rounding, iterative rounding, the primal dual method, lagrangean relaxation, as well as semidefinite programming based approximation algorithms. We will also examine approximations derived from greedy algorithms, local search, dynamic programming, random sampling and metric embeddings.

Students will be expected to have a basic knowledge of algorithms, discrete mathematics and linear programming (a brief introduction will be given initially).
Prerequisites: COS 226, COS 341, COS 423 (or equivalent). Recommended: COS 521

Problem sets will be handed out in class every two weeks. There will be a take home final exam. All students (credit as well as audit) will be expected to scribe lecture notes for some classes during the semester. The grade will be based on performance in the problem sets, the final and quality of the scribe notes. 

(Occasionally, we will have lectures from 3:00-5:00 to make up for lost lectures. This will be announced in class.)

Professor: Moses Charikar - 305 CS Building - 258-7477 moses_AT_cs.princeton.edu 
Office Hours: by appointment

Graduate Coordinator: Melissa Lawson - 410 CS Building - 258-1746 mml_AT_cs.princeton.edu

Course Secretary: Mitra Kelly - 323 CS Building - 258-4562 mkelly_AT_cs.princeton.edu

Mailing List:  Send mail to majordomo@cs.princeton.edu with "subscribe cs594" in the message body to subscribe.

Last updated by Moses Charikar, 25-Feb-2003 12:23 AM