近似算法讨论班 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
imported>Etone No edit summary |
imported>Etone No edit summary |
||
| Line 19: | Line 19: | ||
|- | |- | ||
|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.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. | |||
|} | |} | ||
Revision as of 07:33, 13 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 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; bin packing; first-fit; asymptotic PTAS.
Chap.2, 3 of Williamson-Shmoys.