近似算法讨论班 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
imported>Etone No edit summary |
imported>Etone No edit summary |
||
| Line 16: | Line 16: | ||
|bgcolor="#A7C1F2"|Dates||bgcolor="#A7C1F2"|Speakers||bgcolor="#A7C1F2"|Topics | |bgcolor="#A7C1F2"|Dates||bgcolor="#A7C1F2"|Speakers||bgcolor="#A7C1F2"|Topics | ||
|- | |- | ||
|Sept. 26, 2011 ||张弛豪（上海交通大学） ||Chap.1 of Williamson-Shmoys. Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. | |Sept. 26, 2011 ||张弛豪（上海交通大学）||Chap.1 of Williamson-Shmoys. Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. | ||
|- | |- | ||
|Oct. 8, 2011 ||张弛豪（上海交通大学） ||Chap.2 of Williamson-Shmoys. Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. | |Oct. 8, 2011 ||张弛豪（上海交通大学）||Chap.2 of Williamson-Shmoys. Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. | ||
|} | |} | ||
Revision as of 16:11, 9 October 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.