# 近似算法讨论班 (Fall 2011)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

# 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.
• Michel Goemans. Linear Programming. Lecture notes of Advanced Algorithms class at MIT.
• Venkatesan Guruswami and Ryan O'Donnell. The PCP Theorem and Hardness of Approximation.

# Schedule

 老师出差，暂停一次。 Dates Speakers Topics Readings 9.26 张驰豪（上海交通大学） Introduction to approximation algorithms. Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. Chap. 1 ofWilliamson-Shmoys. 10.8 张驰豪（上海交通大学） Greedy algorithms and local search. Scheduling with deadlines; ${\displaystyle k}$-center; minimize makespan; metric TSP; min-degree spanning tree. Chap. 2.1-2.4 ofWilliamson-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 ofWilliamson-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 ofWilliamson-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. 11.24 朱小虎张驰豪（上海交通大学） The Steiner tree problem. 12.1 詹宇森张驰豪（上海交通大学） Prize-collection 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.