近似算法讨论班 (Fall 2011)

From TCS Wiki
Revision as of 06:15, 17 November 2011 by imported>Etone (→‎Schedule)
Jump to navigation Jump to search

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
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
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
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);
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
Williamson-Shmoys.
11.17 张驰豪
(上海交通大学)
The primal-dual method. Chap. 7.1-7.4
Williamson-Shmoys.