Dates

Speakers

Topics

Readings

9.26

张驰豪 （上海交通大学） 
Introduction to approximation algorithms. Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. 
Chap. 1 of WilliamsonShmoys.

10.8

张驰豪 （上海交通大学） 
Greedy algorithms and local search. Scheduling with deadlines; $k$center; minimize makespan; metric TSP; mindegree spanning tree. 
Chap. 2.12.4 of WilliamsonShmoys.

10.13

詹宇森 蒋炎岩 尹一通 
Local search (cont.). Scale and round. Mindegree spanning tree; local search; potential analysis; Knapsack; dynamic programming; pseudopolynomial time; scale and round; FPTAS. 
Chap. 2.6, 3.1 of WilliamsonShmoys.

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 MAXCUT. MAXCUT; the probabilistic method; semidefinite programming (SDP); rounding SDP; inapproximability; gapreduction; 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 WilliamsonShmoys. PCP lecture at UW by Guruswami and O'Donnell

11.10

张驰豪 （上海交通大学） 尹一通 
Scale and round (cont.). Deterministic rounding of LP. Bin packing; firstfit; exhaustive search; polynomialtime 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.14.3 of WilliamsonShmoys.

11.17

张驰豪 （上海交通大学） 
The primaldual method. 
Chap. 7.17.4 of WilliamsonShmoys.

11.24

朱小虎 张驰豪 （上海交通大学） 
The Steiner tree problem. 

12.1

詹宇森 张驰豪 （上海交通大学） 
Prizecollection Steiner tree; rounding; derandomization. 

12.8

陈嘉 
Algorithmic Game Theory. Strategic games; mechanism design; combinatorial auction; Vickrey auction; VCG auction. 

12.15

尹一通 
Approximate counting; correlation decay; spin systems. 
