General note: The topic this quarter is geometric approximation algorithms. The intention is to really go into the details of the arguments. In many of these works, the proof techniques are at least as interesting and important as the results themselves. These techniques recur through many different works and, once understood, can be used in our own research.


 

Dates: Wednesday, January 11
Topic: Approximating convex polytopes
Paper 1: Pankaj K. Agarwal, Sariel Har-Peled, Micha Sharir, Kasturi R. Varadarajan: Approximating shortest paths on a convex polytope in three dimensions. J. ACM 44(4): 567-584 (1997). PDF file for this paper.
Paper 2: Gill Barequet, Sariel Har-Peled: Efficiently Approximating the Minimum Volume Bounding Box of a Point Set in Three Dimensions. J. Algorithms 38(1): 91-109 (2001). PDF file for this paper.
Speakers: Daniel Russel ( slides ) and An Nguyen ( slides )
Dates: Wednesday, January 18
Topic: Potpourri
Paper 1: Timothy M. Chan: Approximating the Diameter, Width, Smallest Enclosing Cylinder, and Minimum-Width Annulus. Int. J. Comput. Geometry Appl. 12(1-2): 67-85 (2002). PDF file for this paper.
Paper 2: Bernard Chazelle, Ding Liu, Avner Magen: Sublinear geometric algorithms. STOC 2003: 531-540. PDF file for this paper.
Speakers: Siddhartha Chaudhuri ( slides ) and Michael Wand ( slides )
Date: Wednesday, January 25
Topic: Coresets I
Paper: Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan: Approximating extent measures of points. J. ACM 51(4): 606-635 (2004). PDF file for this paper.
  • 2 people, 90 minutes for this paper. The idea is to carefully and thoroughly go over the technical details of this key work.
  • For context, feel free to refer to Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan: Geometric Approximation via Coresets, 2005. PDF file for this paper.
Speakers: Nikola Milosavljevic ( slides )
Date: Wednesday, February 1
Topic: Coresets II
Paper:

Sariel Har-Peled, Yusu Wang: Shape Fitting with Outliers. SIAM J. Comput. 33(2): 269-285 (2004). PDF file for this paper.

Speaker: Emilio Antunez ( slides )
Dates: Wednesday, February 8
Topic: No session
Dates: Wednesday, February 15
Topic: TSP and related problems, I
Paper:

Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM 45(5): 753-782 (1998). PDF file for this paper.

  • 90 minutes for this paper. The idea is to carefully and thoroughly go over the technical details of this key work.
  • For context, feel free to refer to Sanjeev Arora: Approximation Schemes for NP-hard geometric optimization problems: A survey. Math Programming (2003). PDF file for this paper.
Speaker: Steve Oudot ( slides )
Dates: Wednesday, February 22
Topic: TSP and related problems (II), coresets (III)
Paper 1: Satish Rao, Warren D. Smith: Approximating Geometrical Graphs via "Spanners" and "Banyans". STOC 1998: 540-550. PDF file for this paper.
Paper 2: Timothy M. Chan: Faster core-set constructions and data stream algorithms in fixed dimensions. Symposium on Computational Geometry 2004: 152-159. PDF file for this paper.
Speakers: Maksim Ovsjanikovs ( slides ) and Eugene Fratkin ( slides )
Date: Wednesday, March 1
Topic: Clustering I
Papers 1: Sanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation Schemes for Euclidean k-Medians and Related Problems. STOC 1998: 106-113. PDF file for this paper.

Stavros G. Kolliopoulos, Satish Rao: A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem. ESA 1999: 378-389. PDF file for this paper.
Paper 2: Jiri Matousek: On Approximate Geometric k-Clustering. Discrete &
Computational Geometry 24(1): 61-84 (2000). PDF file for this paper.
Speakers: Niloy Mitra ( slides ) and Natasha Gelfand ( slides )
Date: Wednesday, March 8
Topic: Clustering II
Paper 1:

Mihai Badoiu, Sariel Har-Peled, Piotr Indyk: Approximate
clustering via core-sets. STOC 2002: 250-257. PDF file for this paper.
Paper 2: Sariel Har-Peled, Soham Mazumdar: On coresets for k-means and
k-median clustering. STOC 2004: 291-300. PDF file for this paper.
Speakers: Qing Fang ( slides ) and Primoz Skraba ( slides )
Date: Wednesday, March 15
Topic: Clustering III
Paper 1:

Sariel Har-Peled, Akash Kushal: Smaller coresets for k-median and
k-means clustering. Symposium on Computational Geometry 2005:
126-134. PDF file for this paper.
Paper 2: Amit Kumar, Yogish Sabharwal, Sandeep Sen: A Simple Linear Time
Approximation Algorithm for k-Means Clustering in Any
Dimensions. FOCS 2004: 454-462. PDF file for this paper.

For optional material and context, see also Amit Kumar, Yogish Sabharwal, Sandeep Sen: Linear Time Algorithms for Clustering Problems in Any Dimensions. ICALP 2005: 1374-1385. PDF file for this paper.
Speakers: Sergei Vassilvitskii ( slides )