Revision as of 16:07, 13 October 2011

Syllabus

Vijay Vazirani. Approximation Algorithms. Springer, 2004.
David Williamson and David Shmoys. The Design of Approximation Algorithms. Cambridge Univ Press, 2011.

Dates	Speakers	Topics
9.26	张弛豪（上海交通大学）	Introduction to approximation algorithms. Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. Chap.1 of Williamson-Shmoys.
10.8	张弛豪（上海交通大学）	Greedy algorithms and local search. Scheduling with deadlines; [math]\displaystyle{ k }[/math]-center; minimize makespan; metric TSP; min-degree spanning tree. Chap.2 of Williamson-Shmoys.
10.13	詹宇森、蒋炎岩、尹一通	Local search (cont.). Scale and round Min-degree spanning tree; local search; potential analysis; Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS. Chap.2, 3 of Williamson-Shmoys.

@@ Line 20: / Line 20: @@
 |10.8 ||张弛豪（上海交通大学）|| Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. <br> Chap.2 of Williamson-Shmoys.
 |-
-|10.13 ||詹宇森、蒋炎岩、尹一通|| Local search (cont.). Scale and round<br> Min-degree spanning tree; local search; potential analysis; <br>Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS; bin packing; first-fit; asymptotic PTAS.<br> Chap.2, 3 of Williamson-Shmoys.
+|10.13 ||詹宇森、蒋炎岩、尹一通|| Local search (cont.). Scale and round<br> Min-degree spanning tree; local search; potential analysis; <br>Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS.<br> Chap.2, 3 of Williamson-Shmoys.
 |}