imported>Etone |
imported>Etone |
| Line 1: |
Line 1: |
| = Syllabus = | | == Problem 1== |
| *'''Time''': every Thursday, 6:30pm.
| |
| * '''Place''': CS building, 228.
| |
|
| |
|
| * '''Organizer''': 尹一通
| | ==Problem 2== |
| :* office: CS building, 804
| | 一个图 <math>G(V,E)</math> 的切 (cut) 是一个边集 <math>C\subseteq E</math>，使得去掉这些边之后 <math>G</math> 不再连通。 |
| :* email: yitong.yin@gmail.com
| |
|
| |
|
| === Reference materials ===
| | 证明：任意一个有 <math>m</math> 条边的图都存在一个大小为 <math>\frac{m}{2}</math> 的切。 |
| * Vijay Vazirani. ''Approximation Algorithms''. Springer, 2004.
| |
| * 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 = | | ==Problem 3 == |
| :{|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;"
| | 令 <math>\mathcal{F}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-regular family，即 <math>\forall i\in[n]</math>，刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{F}</math> 满足 <math>i\in S</math>。 |
| |-
| | |
| |bgcolor="#A7C1F2" align="center"|'''Dates'''
| | 假设 <math>k\ge 10</math>。证明：存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{F}</math> 中不存在单色的集合 <math>S\in\mathcal{F}</math>。 |
| |bgcolor="#A7C1F2" align="center"|'''Speakers'''
| |
| |bgcolor="#A7C1F2" align="center"|'''Topics'''
| |
| |bgcolor="#A7C1F2" align="center"|'''Readings'''
| |
| |-
| |
| |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
| |
| |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
| |
| |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
| |
| !colspan="3"|<font color=red>老师出差，暂停一次。</font>
| |
| |-
| |
| |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.
| |
| |}
| |
Problem 1
Problem 2
一个图 [math]\displaystyle{ G(V,E) }[/math] 的切 (cut) 是一个边集 [math]\displaystyle{ C\subseteq E }[/math]，使得去掉这些边之后 [math]\displaystyle{ G }[/math] 不再连通。
证明：任意一个有 [math]\displaystyle{ m }[/math] 条边的图都存在一个大小为 [math]\displaystyle{ \frac{m}{2} }[/math] 的切。
Problem 3
令 [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-regular family，即 [math]\displaystyle{ \forall i\in[n] }[/math]，刚好有 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ S\in\mathcal{F} }[/math] 满足 [math]\displaystyle{ i\in S }[/math]。
假设 [math]\displaystyle{ k\ge 10 }[/math]。证明：存在一个对 [math]\displaystyle{ [n] }[/math] 的 2着色 [math]\displaystyle{ f:[n]\rightarrow\{0,1\} }[/math] 使得 [math]\displaystyle{ \mathcal{F} }[/math] 中不存在单色的集合 [math]\displaystyle{ S\in\mathcal{F} }[/math]。