Date 
Topic 
Speaker 
9/17/01 
Introduction: Set Cover 
Moses 
9/24/01 
Facility Location and kMedian 
Moses 
10/1/01 
Facility Location and kMedian (primaldual) 
Moses 
10/8/01 
Asymmetric pcenter (paper 1) 
Stavros 
10/15/01 
cancelled due to FOCS'01 

10/17/01 
Binpacking and Knapsack (guest lecture)
(exercises) 
Chandra Chekuri 
10/22/01 
Metric Methods (multicut, balanced cut) 
Moses 
10/26/01 
Probabilistic Approximation of Metric Spaces via Trees 
Moses 
10/29/01 
cancelled due to Fall Break 

11/5/01 
Local Search for kMedian (paper 3) 
Amit 
11/12/01 
Directed Steiner tree (paper 2) 
Tony 
11/19/01 
Multiway Cut (paper 6)
(slides)

Renato 
11/26/01 
Single Sink Edge Installation (paper 4) 
Ding 
12/3/01 
PTAS for geometric kclustering (paper 9) 
Manoj 
12/10/01 
Classification Problems with Pairwise Relationships (paper 7) 
Adriana 