近似算法讨论班 (Fall 2011)

Syllabus

• Time: every Thursday, 6:30pm.
• Place: CS building, 228.

• Organizer: 尹一通

• office: CS building, 804
• email: yitong.yin@gmail.com

Reference materials

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

Schedule

Dates	Speakers	Topics
Sept. 26, 2011	张弛豪（上海交通大学）	Chap.1 of Williamson-Shmoys. Introduction to approximation algorithms. Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms.
Oct. 8, 2011	张弛豪（上海交通大学）	Chap.2 of Williamson-Shmoys. Greedy algorithms and local search. Scheduling with deadlines; [math]\displaystyle{ k }[/math]-center; minimize makespan; metric TSP; min-degree spanning tree.