| 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 LP
|
| 11.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'Donnell
|
| 11.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.
|