Theory Seminar Series
Fall 04 Session
(Approximation Algorithms)
Venue: 347 Avery Hall
Time: 2.30-3.30 pm
Approximate Schedule
- Wed, 9/1
Chapters 2-3 (not Sec 2.3): Set Cover and Steiner Tree and TSP
Geng Hao
- Wed, 9/8
Geng Continued.
- Wed, 9/15
Section 2.3 and Chapter 7: Shortest Superstring
Cory Strope
- Wed, 9/22
Cory Strope: Shortest Superstring (Cont.)
- Wed, 9/29
Chapter 28+: Counting Problems
Deng Kun
- Wed, 10/6
Deng Kun: Counting Problems (Cont.)
- Wed, 10/13
Chapter 29: Hardness of Approximation
Chris Bourke
- Wed, 10/20
Chapter 29 (cont'd): Hardness of Approximation
Chris Bourke
- Wed, 10/27
Chapters 12, 13: LP-Duality and Set Cover via Dual Filtering
- Wed, 11/3
Chapters 14, 15: Set Cover via Rounding and Primal-Dual Schema
- Wed, 11/10
Chapter 21: Sparsest Cut
- Wed, 11/17
Chapter 21 (cont'd): Sparsest Cut
- Wed, 12/1
Chapters 22, 23: Steiner Forest and Network
- Wed, 12/8
Chapter 30: Open Problems