6.891 Spring 2000
These are the lecture notes for MIT course 6.891, "Approximation algorithms", taught by
David P. Williamson
in Spring 2000.
Handouts
Handout 1: Course Information
Lecture notes from Fall 1998 class at Cornell
Scribe notes
Lecture 1: Intro to approximation algorithms, set cover
Lecture 2: Bin packing.
Lecture 3: Randomization: MAX SAT.
Lecture 4: Randomization: 3-coloring and MAX CUT in dense graphs.
Lecture 5: Semidefinite programming: MAX CUT, graph coloring.
Lecture 6: Semidefinite programming: Quadratic programming. Scheduling problems.
Lecture 7: Dynamic programming: Arora's PTAS for Euclidean TSP.
Lecture 8: Primal-dual method: Feedback vertex set, shortest s-t path, generalized Steiner trees.
Lecture 9: Uncapacitated facility location: deterministic rounding, randomized rounding, primal-dual algorithm.
Lecture 10: Lagrangean relaxation: the k-median problem. Minimum multicut.
Lecture 11: Metric methods: Minimum multicut. Balanced cuts.
Lecture 12: Deterministic rounding: Jain's technique for survivable network design.