近似算法讨论班 (Fall 2011)

From TCS Wiki
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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 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.
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.
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=近似算法讨论班_(Fall_2011)&oldid=5088"