Theory Seminar Series
Fall 04 Session (Approximation Algorithms)

Venue: 347 Avery Hall
Time: 2.30-3.30 pm

Approximate Schedule

  1. Wed, 9/1
    Chapters 2-3 (not Sec 2.3): Set Cover and Steiner Tree and TSP
    Geng Hao

  2. Wed, 9/8
    Geng Continued.

  3. Wed, 9/15
    Section 2.3 and Chapter 7: Shortest Superstring
    Cory Strope

  4. Wed, 9/22
    Cory Strope: Shortest Superstring (Cont.)

  5. Wed, 9/29
    Chapter 28+: Counting Problems
    Deng Kun

  6. Wed, 10/6
    Deng Kun: Counting Problems (Cont.)

  7. Wed, 10/13
    Chapter 29: Hardness of Approximation
    Chris Bourke

  8. Wed, 10/20
    Chapter 29 (cont'd): Hardness of Approximation
    Chris Bourke

  9. Wed, 10/27
    Chapters 12, 13: LP-Duality and Set Cover via Dual Filtering

  10. Wed, 11/3
    Chapters 14, 15: Set Cover via Rounding and Primal-Dual Schema

  11. Wed, 11/10
    Chapter 21: Sparsest Cut

  12. Wed, 11/17
    Chapter 21 (cont'd): Sparsest Cut

  13. Wed, 12/1
    Chapters 22, 23: Steiner Forest and Network

  14. Wed, 12/8
    Chapter 30: Open Problems