近似算法讨论班 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
imported>Etone (Created page with "= Syllabus = *'''Time''': every Thursday, 6:30pm. * '''Place''': CS building, 228. * '''Organizer''': 尹一通 :* office: CS building, 804 :* email: yitong.yin@gmail.com = Sc…") |
imported>Etone No edit summary |
||
| Line 6: | Line 6: | ||
:* office: CS building, 804 | :* office: CS building, 804 | ||
:* email: yitong.yin@gmail.com | :* 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 = | = Schedule = | ||
Revision as of 16:06, 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.