近似算法讨论班 (Fall 2011): Difference between revisions
Jump to navigation
Jump to search
imported>Etone |
imported>Etone |
||
| Line 17: | Line 17: | ||
|- | |- | ||
|9.26 | |9.26 | ||
|align="center"|张驰豪<br>（上海交通大学）|| Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms.||Chap.1<br>Williamson-Shmoys. | |align="center"|张驰豪<br>（上海交通大学）|| Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms.||Chap. 1 of<br>Williamson-Shmoys. | ||
|- | |- | ||
|10.8 | |10.8 | ||
|align="center"|张驰豪<br>（上海交通大学）|| Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. || Chap. 2.1-2.4<br>Williamson-Shmoys. | |align="center"|张驰豪<br>（上海交通大学）|| Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. || Chap. 2.1-2.4 of<br>Williamson-Shmoys. | ||
|- | |- | ||
|10.13 | |10.13 | ||
|align="center"|詹宇森<br>蒋炎岩<br>尹一通|| 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.||Chap. 2.6, 3.1<br>Williamson-Shmoys. | |align="center"|詹宇森<br>蒋炎岩<br>尹一通|| 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.||Chap. 2.6, 3.1 of<br>Williamson-Shmoys. | ||
|- | |- | ||
|10.20 | |10.20 | ||
| Line 34: | Line 34: | ||
|11.4 | |11.4 | ||
|align="center"| 周源 <br>(Carnegie Mellon University)|| Approximation (and inapproximability) of MAX-CUT.<br> MAX-CUT; the probabilistic method; semi-definite programming (SDP); rounding SDP;<br> inapproximability; gap-reduction; probabilistically checkable proofs (PCP); the PCP theorem; <br> label cover game; parallel repetition theorem; unique label cover game; the unique games conjecture (UGC); <br> Boolean function; Fourier transformation; Parseval's identity; influence; noise operator; stability;<br>long code reduction; majority is the stablest (MIS); | |align="center"| 周源 <br>(Carnegie Mellon University)|| Approximation (and inapproximability) of MAX-CUT.<br> MAX-CUT; the probabilistic method; semi-definite programming (SDP); rounding SDP;<br> inapproximability; gap-reduction; probabilistically checkable proofs (PCP); the PCP theorem; <br> label cover game; parallel repetition theorem; unique label cover game; the unique games conjecture (UGC); <br> Boolean function; Fourier transformation; Parseval's identity; influence; noise operator; stability;<br>long code reduction; majority is the stablest (MIS); | ||
||Chap. 6.1, 6.2<br>Williamson-Shmoys.<br>[http://www.cs.washington.edu/education/courses/cse533/05au/ PCP lecture at UW]<br> by Guruswami and O'Donnell | ||Chap. 6.1, 6.2 of<br>Williamson-Shmoys.<br>[http://www.cs.washington.edu/education/courses/cse533/05au/ PCP lecture at UW]<br> by Guruswami and O'Donnell | ||
|- | |- | ||
|11.10 | |11.10 | ||
|align="center"|张驰豪<br>（上海交通大学）<br>尹一通|| Scale and round (cont.). Deterministic rounding of LP. <br> Bin packing; first-fit; exhaustive search; polynomial-time approximation scheme (PTAS). <br>Scheduling on a single machine; completion time; preemptive; shortest remaining processing time (SRPT); <br>the ellipsoid algorithm; separation oracle. || Chap. 3.3, 4.1-4.3 <br> Williamson-Shmoys. | |align="center"|张驰豪<br>（上海交通大学）<br>尹一通|| Scale and round (cont.). Deterministic rounding of LP. <br> Bin packing; first-fit; exhaustive search; polynomial-time approximation scheme (PTAS). <br>Scheduling on a single machine; completion time; preemptive; shortest remaining processing time (SRPT); <br>the ellipsoid algorithm; separation oracle. || Chap. 3.3, 4.1-4.3 of<br> Williamson-Shmoys. | ||
|- | |- | ||
|11.17 | |11.17 | ||
|align="center"|张驰豪<br>（上海交通大学）|| The primal-dual method. || Chap. 7.1-7.4 <br> Williamson-Shmoys. | |align="center"|张驰豪<br>（上海交通大学）|| The primal-dual method. || Chap. 7.1-7.4 of<br> Williamson-Shmoys. | ||
|} | |} | ||
Revision as of 06:20, 17 November 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 Readings 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.1-2.4 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.6, 3.1 of
Williamson-Shmoys.10.20 老师出差，暂停一次。 10.27 陈嘉 Linear Programming.
Linear Programming; the simplex method; duality; strong duality theorem; von Neumann's minmax theorem.[slides]
Geomans' notes on LP11.4 周源
(Carnegie Mellon University)Approximation (and inapproximability) of MAX-CUT.
MAX-CUT; the probabilistic method; semi-definite programming (SDP); rounding SDP;
inapproximability; gap-reduction; probabilistically checkable proofs (PCP); the PCP theorem;
label cover game; parallel repetition theorem; unique label cover game; the unique games conjecture (UGC);
Boolean function; Fourier transformation; Parseval's identity; influence; noise operator; stability;
long code reduction; majority is the stablest (MIS);Chap. 6.1, 6.2 of
Williamson-Shmoys.
PCP lecture at UW
by Guruswami and O'Donnell11.10 张驰豪
（上海交通大学）
尹一通Scale and round (cont.). Deterministic rounding of LP.
Bin packing; first-fit; exhaustive search; polynomial-time approximation scheme (PTAS).
Scheduling on a single machine; completion time; preemptive; shortest remaining processing time (SRPT);
the ellipsoid algorithm; separation oracle.Chap. 3.3, 4.1-4.3 of
Williamson-Shmoys.11.17 张驰豪
（上海交通大学）The primal-dual method. Chap. 7.1-7.4 of
Williamson-Shmoys.