近似算法讨论班 (Fall 2011): Difference between revisions

From TCS Wiki
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.