近似算法讨论班 (Fall 2011)
Revision as of 15:51, 9 October 2011 by Etone (Created page with "= Syllabus = *'''Time''': every Thursday, 6:30pm. * '''Place''': CS building, 228. * '''Organizer''': 尹一通 :* office: CS building, 804 :* email: firstname.lastname@example.org = Sc…")
- Time: every Thursday, 6:30pm.
- Place: CS building, 228.
- Organizer: 尹一通
- office: CS building, 804
- email: email@example.com
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; -center; minimize makespan; metric TSP; min-degree spanning tree.