6.891 Spring 2000 Home Page
This is the home page for MIT course 6.891, "Approximation algorithms", for the Spring 2000 term.
David P. Williamson
(914) 945-1743
dpw@watson.ibm.com
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.
Problem Sets
Problem set 0
Problem set 1
Problem set 2
Problem set 3
Problem set 4
Problem Set Solutions
Problem set 1 solutions
Problem set 2 solutions
Problem set 3 solutions
Problem set 4 solutions