Princeton University
Computer Science Department

Computer Science 594
Approximation Algorithms 

Moses Charikar

Spring 2003

 

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

Approximate Schedule

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: 

Homeworks

Homework 1 (due Mon, Mar 10) (ps,pdf)

Homework 2 (due Mon, Apr 14) (ps,pdf)

 

References

 

  1. Michel Goeman's notes on Linear Programming
    (Read Sections 1-6 and 8-10).

  2. David P. Williamson's lecture notes on Approximation Algorithms.

 

 Lecture Notes

 

  1. 2/03/03 (ps,pdf)   John White

  2. 2/05/03 (ps,pdf)   Satyen Kale

  3. 2/10/03 (ps,pdf)   

  4. 2/17/03 (ps,pdf)

 

 

Template for scribe notes. Sample LaTeX files (1.tex,2.tex,3.tex,4.tex,5.tex)

Last updated by Moses Charikar, 02-Apr-2003 02:49 PM