CS 598 TMC, Fall 2018

Geometric Approximation Algorithms

Instructor

Meeting Time and Place

Course Overview

We will study a variety of fundamental problems, chosen to illustrate important techniques in the area. (Occasionally, we will touch on some recent research results and open questions.) Possible topics include:

• Extent-related problems: diameter, width, minimum bounding box (techniques: grids, epsilon-kernels/coresets, polytope approximation, a recent polynomial method)
• Range-counting-related problems (techniques: random sampling, Chernoff bounds, discrepancy, shallow cuttings)
• Proximity-related problems: closest pair, nearest neighbors, Euclidean spanners, Euclidean minimum spanning trees (techniques: grids, quadtrees, shifting, well-separated pair decomposition)
• NP-hard problems: geometric independent set, set cover, hitting set (techniques: shifted grids/quadtrees, planar-graph separators and geometric separators, local search, LP rounding, union complexity, (<=k)-levels, epsilon-nets, quasi-sampling, multiplicative weights update, APX-hardness)
• Other assorted problems: Euclidean traveling salesman, clustering (k-center/k-median), embedding, shortest paths in unit disk graphs, high-dimensional minimum enclosing ball, ...

Prerequisite: Prior knowledge in computational geometry or approximation algorithms is not required, but a solid background in algorithm design and analysis (e.g., at the level of CS 374) is assumed.

Course Work

• 3 or 4 assignments (problem sets), worth 40%
  • Homework 1 (due Sep 28, Fri) [note (9/14): have changed Q3 to make it less trivial]
  • Homework 2 (due Oct 17, Wed) [note: in Q1, all squares are axis-aligned]
  • Homework 3 (due Nov 9, Fri)
  • Homework 4 (due Dec 5, Wed)
• presentation, worth 20%
• a project (reading some papers and writing a report, or implementing some algorithms, or doing some original research), worth 40%

See guidelines for presentation and project.

References

• [H-P] S. Har-Peled, Geometric Approximation Algorithms, AMS, 2011
• [BCKO] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry: Algorithms and Applications (3rd ed.), Springer-Verlag, 2008
• [GRT] J. Goodman, J. O'Rourke, and C. D. Toth (eds.), Handbook of Discrete and Computational Geometry (3rd ed.), CRC Press, 2017

Piazza

Lectures

(I'll provide copies of my handwritten notes, and links to relevant papers, below...)

Aug 29, 31: The diameter problem

• Constant-approx. algorithms: factor 2 and factor sqrt{3}
• (1+eps)-approx. algorithms in fixed dimensions: 1. rounding points to a grid (O(n + 1/eps^{2(d-1)}) time), 2. rounding directions (O(n/eps^{(d-1)/2})), 3. combination (O(n + 1/eps^{3(d-1)/2})), 4. recursion in dimension (O(n+1/eps^{d-(1/2)}))
• Refs: my notes, my paper (2002) [Sec 2, Algorithms 1-4]

Sep 5: The diameter problem (cont'd)

• Polynomial method: Chebyshev polynomials + Chinese remainder + convolution (O~(n/sqrt{eps} + n/eps^{(d+1)/2}) time)
• Refs: my notes, my paper (SoCG 2017) [Lemma 2 and Sec 5], wikipedia entry on Chebyshev polynomials

Sep 7: The width problem

• First (1+eps)-approx algorithm: rounding directions + linear programming (O(n/eps^{(d-1)/2}) time)
• Second algorithm: epsilon-kernels/coresets...
• Refs: my notes, my paper (2002) [Sec 3, Algorithm 1]

Sep 12, 14, 19: epsilon-kernels/coresets

• Algorithms: 1. fattening + rounding points (O(1/eps^{d-1}) size), 2. fattening + rounding directions (O(1/eps^{d-1}) size), 3. Dudley's technique (O(1/eps^{(d-1)/2}) size)
• Applications to min enclosing ball/cylinder/box/..., min-width enclosing annulus (by linearization), sketching/streaming, outliers
• Refs: my notes (part 1 and part 2), Agarwal, Har-Peled, and Varadarajan's paper (2004) and survey, my paper (2006) [Sec 2]

Sep 21, 26: Approximate range counting problems

• "epsilon-approximations" (with additive error eps*n): random sampling + Chernoff (O((1/eps^2) log (1/eps)) size), improved bounds for balls/halfspaces via discrepancy + matching with low crossing numbers ((O~(1/eps^{2-2/(d+1)}) size)
• Deterministic construction of epsilon-approximations: Matousek's O(n)-time algorithm for constant eps via merge-and-reduce
• Refs: my notes, books on discrepancy theory by Matousek and Chazelle

Sep 28, Oct 3: Approximate range counting problems (cont'd): 1+eps factor

• First method: random sampling with different sizes + Chernoff
• Second method: shallow cuttings
• Refs: my notes, Sariel's book [Ch8], Afshani and C.'s paper (2007) [Sec 2.1-2.2]

Oct 5, 10: Proximity problems: bichromatic closest pair, nearest neighbors

• fixed radius: grid methods (O((1/eps^d)n) time naively, or O((1/eps^{d/4})n) by eps-kernel-related techniques)
• arbitrary radius: compressed quadtrees, balanced quadtrees, shifting (O(n) space and O(log U + 1/eps^d) or O((1/eps^d) log n) query time)
• Refs: my notes, Sariel's book [Ch2], my paper (1998) [Sec 3]

Oct 12, 17: Euclidean min spanning trees, spanners

• Method 1: Yao graph (O(n) size, O(n polylog n) time)
• Method 2: well-separated pair decomposition, via compressed quadtrees (O(n) size, O(n log n) time)
• Refs: my notes, Callahan and Kosaraju's original paper (1995), Sariel's book [Ch3], a short paper of mine (2008)

Oct 19, 24: Geometric independent set, hitting set, set cover

• Technique 0: greedy (O(1) approximation for independent set and piercing for arbitrary fat objects)
• Technique 1: shifted grid (PTAS for (weighted) independent set and piercing for fat objects of similar sizes)
• Technique 2: shifted quadtree (PTAS for (weighted) independent set and piercing for arbitrary fat objects)
• Technique 3: geometric separators, via Smith and Wormald's theorem (PTAS for independent set and piercing for arbitrary fat objects)
• Refs: my notes, Hochbaum and Maass's original paper (1985), my paper (2001)

Oct 26: Geometric independent set, hitting set, set cover (cont'd)

• Technique 4: local search (PTAS for independent set for arbitrary fat objects, and hitting set for 2D disks)
• Refs: my notes, my paper with Sariel (SoCG'09), Mustafa and Ray's paper (SoCG'09)

Oct 31, Nov 2: Geometric independent set (cont'd)

• LP rounding + (<=k)-level (O(1) approximation for independent set for (weighted) objects with low union complexity)
• randomized LP rounding (O(log n/loglog n) approximation for independent set for (weighted) 2D rectangles)
• Refs: my notes, my paper with Sariel (SoCG'09)

Nov 7, 9: Geometric set cover (cont'd)

• LP rounding + epsilon-nets (O(1) approximation for set cover for objects with low union complexity), or multiplicative weights update + epsilon-nets
• LP rounding + weighted epsilon-nets via "quasi-sampling" (O(1) approximation for set cover for weighted objects with low union complexity)
• Refs: my notes (unweighted and weighted), Bronnimann and Goodrich's paper, Varadarajan's and CGKS's quasi-sampling papers

Nov 14, 16: Geometric independent set (cont'd)

• Fox and Pach's separator approach (n^eps approximation for independent set of line segments or curves)
• Adamaszek and Wiese's separator approach (QPTAS for independent set of line segments or curves)
• APX-hardness (for independent set for 3D boxes, and set cover for fat triangles and fat rectangles)
• Refs: my notes, papers by Fox and Pach, Adamaszek, Har-Peled, and Wiese, Har-Peled, and Grant and me

Nov 28: Euclidean traveling salesman

• Arora's PTAS (the version with n^{O(1/eps)} runtime)
• Refs: my notes, Arora's survey or journal paper

Nov 30, Dec 5: Min enclosing ball in high dimensions

• Badoiu, Har-Peled, and Indyk's algorithm, as analyzed by Badoiu and Clarkson (coreset of size O(1/eps), without dependencies on d)
• another iterative algorithm by Badoiu and Clarkson (in O((1/eps)^2 dn) time)
• 1-pass streaming algorithms (factor 3/2 by Zarrabi-Zadeh and C., and factor sqrt{2} by Agarwal and Sharathkumar)
• Refs: my notes, Badoiu and Clarkson (2003), Zarrabi-Zadeh and C. (2006), Agarwal and Sharathkumar (2010), C. and Pathak (2013)

Dec 7, 12: Student presentations