Princeton University
Computer Science Department

Computer Science 594
Approximation Algorithms

Moses Charikar

Spring 2003


General Information | Schedule and Readings | What's New?

Course Description

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. 

Syllabus (tentative)

Week 1: Introduction, Set Cover.

Week 2: Bin Packing

Week 3: Bin Packing contd.

Week 4: Randomization: MAX SAT, MAX CUT for dense graphs

Week 5: MAX CUT contd., Semidefinite programming

Week 6

Week 7

Week 8

Week 9

Week 10

Week 11

Week 12


Administrative Information

Lectures: MW 3:00-4:20 , Room: 401 

(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 
Office Hours: by appointment

Graduate Coordinator: Melissa Lawson - 410 CS Building - 258-1746

Course Secretary: Mitra Kelly - 323 CS Building - 258-4562

Mailing List:  Send mail to with "subscribe cs594" in the message body to subscribe.

Teaching Assistants: none

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