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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
Line 24: Line 24:
|10.20||<font color=red>老师出差,暂停一次。</font>||
|10.20||<font color=red>老师出差,暂停一次。</font>||
|-
|-
|10.27|| 陈嘉||  Linear Programming. <br> Linear Programming; the simplex method; duality; strong duality theorem; von Neumann's minmax theorem.
|10.27|| 陈嘉||  Linear Programming. [[media:Lp_no_pause.pdf‎|<nowiki>[</nowiki>slides<nowiki>]</nowiki>]]<br> Linear Programming; the simplex method; duality; strong duality theorem; von Neumann's minmax theorem.
|}
|}

Revision as of 03:38, 29 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.
Chap.2, 3 of Williamson-Shmoys.
10.20 老师出差,暂停一次。
10.27 陈嘉 Linear Programming. [slides]
Linear Programming; the simplex method; duality; strong duality theorem; von Neumann's minmax theorem.