Princeton University 
Computer Science
594


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.
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.
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: 
(Occasionally, we will have lectures from 3:005:00 to make up for lost lectures. This will be announced in class.)
Professor: Moses Charikar 
305 CS Building  2587477 moses_AT_cs.princeton.edu
Office Hours: by appointment
Graduate Coordinator: Melissa Lawson  410 CS Building  2581746 mml_AT_cs.princeton.edu
Course Secretary: Mitra Kelly  323 CS Building  2584562 mkelly_AT_cs.princeton.edu
Mailing List: Send mail to majordomo@cs.princeton.edu with "subscribe cs594" in the message body to subscribe.
Teaching Assistants: noneLast updated by Moses Charikar, 25Feb2003 12:23 AM