近似算法讨论班 (Fall 2011): Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
imported>Etone
imported>Etone
 
(10 intermediate revisions by the same user not shown)
Line 10: Line 10:
* Vijay Vazirani. ''Approximation Algorithms''. Springer, 2004.
* Vijay Vazirani. ''Approximation Algorithms''. Springer, 2004.
* David Williamson and David Shmoys. ''The Design of Approximation Algorithms''. Cambridge Univ Press, 2011.
* David Williamson and David Shmoys. ''The Design of Approximation Algorithms''. Cambridge Univ Press, 2011.
* Michel Goemans. [http://www-math.mit.edu/~goemans/notes-lp.ps ''Linear Programming'']. Lecture notes of ''Advanced Algorithms'' class at MIT.
* Venkatesan Guruswami and Ryan O'Donnell. [http://www.cs.washington.edu/education/courses/cse533/05au/ ''The PCP Theorem and Hardness of Approximation''].


= Schedule =
= Schedule =
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
|-
|bgcolor="#A7C1F2"|Dates||bgcolor="#A7C1F2"|Speakers||bgcolor="#A7C1F2"|Topics
|bgcolor="#A7C1F2" align="center"|'''Dates'''
|bgcolor="#A7C1F2" align="center"|'''Speakers'''
|bgcolor="#A7C1F2" align="center"|'''Topics'''
|bgcolor="#A7C1F2" align="center"|'''Readings'''
|-
|-
|9.26 ||张弛豪（上海交通大学）|| Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms. <br>Chap.1 of Williamson-Shmoys.
|9.26  
|align="center"|张驰豪<br>（上海交通大学）|| Introduction to approximation algorithms.<br> Approximation ratio; set cover; rounding an LP; LP duality; greedy algorithms.||Chap. 1 of<br>Williamson-Shmoys.
|-
|-
|10.8 ||张弛豪（上海交通大学）|| Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. <br> Chap.2 of Williamson-Shmoys.
|10.8  
|align="center"|张驰豪<br>（上海交通大学）|| Greedy algorithms and local search.<br> Scheduling with deadlines; <math>k</math>-center; minimize makespan; metric TSP; min-degree spanning tree. || Chap. 2.1-2.4 of<br>Williamson-Shmoys.
|-
|-
|10.13 ||詹宇森、蒋炎岩、尹一通|| Local search (cont.). Scale and round<br> Min-degree spanning tree; local search; potential analysis; <br>Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS.<br> Chap.2, 3 of Williamson-Shmoys.
|10.13  
|align="center"|詹宇森<br>蒋炎岩<br>尹一通|| Local search (cont.). Scale and round.<br> Min-degree spanning tree; local search; potential analysis; <br>Knapsack; dynamic programming; pseudo-polynomial time; scale and round; FPTAS.||Chap. 2.6, 3.1 of<br>Williamson-Shmoys.
|-
|-
|10.20||<font color=red>老师出差，暂停一次。</font>||
|10.20
!colspan="3"|<font color=red>老师出差，暂停一次。</font>
|-
|-
|10.27|| 陈嘉、尹一通||  Scale and round(cont.) <br> bin packing; first-fit; exhaustive search; PTAS. <br> Linear Programming. <br> Duality; strong duality theorem; von Neumann's minmax theorem.
|10.27
|align="center"| 陈嘉||  Linear Programming.<br> Linear Programming; the simplex method; duality; strong duality theorem; von Neumann's minmax theorem.
|| [[media:Lp_no_pause.pdf‎|<nowiki>[</nowiki>slides<nowiki>]</nowiki>]]<br>[http://www-math.mit.edu/~goemans/notes-lp.ps Geomans' notes on LP]
|-
|11.4
|align="center"| 周源 <br>(Carnegie Mellon University)|| Approximation (and inapproximability) of MAX-CUT.<br> MAX-CUT; the probabilistic method; semi-definite programming (SDP); rounding SDP;<br> inapproximability; gap-reduction; probabilistically checkable proofs (PCP); the PCP theorem; <br> label cover game; parallel repetition theorem; unique label cover game; the unique games conjecture (UGC); <br> Boolean function; Fourier transformation; Parseval's identity; influence; noise operator; stability;<br>long code reduction; majority is the stablest (MIS);
||Chap. 6.1, 6.2 of<br>Williamson-Shmoys.<br>[http://www.cs.washington.edu/education/courses/cse533/05au/ PCP lecture at UW]<br> by Guruswami and O'Donnell
|-
|11.10
|align="center"|张驰豪<br>（上海交通大学）<br>尹一通|| Scale and round (cont.). Deterministic rounding of LP. <br> Bin packing; first-fit; exhaustive search; polynomial-time approximation scheme (PTAS). <br>Scheduling on a single machine; completion time; preemptive; shortest remaining processing time (SRPT); <br>the ellipsoid algorithm; separation oracle. || Chap. 3.3, 4.1-4.3 of<br> Williamson-Shmoys.
|-
|11.17
|align="center"|张驰豪<br>（上海交通大学）|| The primal-dual method. || Chap. 7.1-7.4 of<br> Williamson-Shmoys.
|-
|11.24
|align="center"|朱小虎<br>张驰豪<br>（上海交通大学）|| The Steiner tree problem. ||
|-
|12.1
|align="center"|詹宇森<br>张驰豪<br>（上海交通大学）|| Prize-collection Steiner tree; rounding; derandomization. ||
|-
|12.8
|align="center"|陈嘉|| Algorithmic Game Theory.<br>Strategic games; mechanism design; combinatorial auction; Vickrey auction; VCG auction. ||
|-
|12.15
|align="center"|尹一通|| Approximate counting; correlation decay; spin systems. ||
|}
|}

Latest revision as of 07:53, 28 December 2011

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"