6.891 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.