15-859(J): Algorithmic Applications of Metric Embeddings

Instructors: Anupam Gupta and R. Ravi

Time: TR 1:30-2:50

Place: Wean 4615A

Course description: 

In recent years, the study of distance-preserving embeddings has given a powerful tool to algorithm designers. This course will study various aspects of embedding of metric spaces into "simpler" ones.

Topics that are likely to be covered include: embeddings of general metric spaces into normed spaces (Bourgain's theorem and its variants), improvements for planar graphs and trees, volume respecting embeddings, embeddings into trees (Bartal's theorems) and their derandomizations, improvements of these results for special metrics, low dimensional embeddings, dimensionality reduction via Johnson-Lindenstrauss lemma, generalizations to non-Euclidean norms via stable distributions. These results will be illustrated by applications to approximation algorithms (e.g., for multicommodity flow, graph bandwidth, mixtures of Gaussians), on-line algorithms (e.g., for metrical task systems), computational geometry (e.g., nearest neighbor), computation with bounded space, etc. 

Lecture Notes

1. Sep 2. Introduction. (AG)
2. Sep 4. Metrics in algorithms. (RR)
3. Sep 9. Metrics in algorithms. Embeddings into l_infinity. (RR)
4. Sep 11. Bourgain's theorem: embeddings into l₁ space. (Notes combined with #5.) (AG)
5. Sep 16. Embeddings into l_p spaces. Finding best Euclidean embeddings. (AG)
6. Sep 18. Lower bounds on embeddings: flows and cuts. (AG)
7. Sep 23. LASTs and Spanners. (RR)
8. Sep 25. Embeddings into tree distributions. (AG)
9. Sep 30. Embeddings into tree distributions: Random graph partitions (AG)
10. Oct 2. Lp Embeddings from Random graph partitions (AG/RR)
11. Oct 7. Tree Covers: Embeddings and Routing Algorithms (AG)
12. Oct 9. Tree Metrics and Ultrametrics (RR)
13. Oct 14. Ultrametrics and subdominance. (RR)
14. Oct 16. Finding closest tree metrics (RR) Random Projections. (AG)
15. Oct 21. Dimensionality Reduction and Random Projections  (AG)
16. Oct 23. Random Projections, Lower Bounds, and embedding l2 into l1. (Notes combined with #15.) (AG)
17. Oct 28. Approximating min-Bandwidth Layouts and Volume Respecting Embeddings. (AG)
18. Oct 30. Volume Respecting Embeddings. (AG/RR)
19. Nov 4. Volume Respecting Embeddings (Notes combined with #20.) (RR)
20. Nov 6. Volume Respecting Embeddings (ends) (RR)
21. Nov 11. Planar partitioning schemes. (RR)
22. Nov 13. Embeddings for special graphs: Cuts and trees. (AG)
23. Nov 18. Embeddings for series-parallel graphs. (AG)
24. Nov 20. Lower bounds for embeddings: algebraic methods. (AG)
25. Nov 25. Near neighbour searching. (AG)
26. Dec 2. Max-Volume Ellipsoids, Convex Geometry and Embeddings. (AG)

Homeworks

1. Homework 1, due Sept 25th.
2. Homework 2, due October 21st.
3. Homework 3, due Nov 11th.

Papers

Here are several books and papers covering topics related to the course. 
This is only a convenient reference list, not a syllabus of any sort. More links
will arrive later.

• Books:

  1. Lectures on Discrete Geometry by Jiri Matousek: Chapter 15 is a survey of metric embeddings.
         Many proofs, exercises, references. Closest thing to a text for the course.
  2. M. Deza and M. Laurent. Geometry of Cuts and Metrics. 
         Book with an emphasis on isometric (exact distance preserving) embeddings.
     
     

• Surveys:

  1. Chapter on embeddings in Handbook of Discrete and Computational Geometry, Jiri Matousek and Piotr Indyk.
         Quick reference on many topics.
  2. Survey by Piotr Indyk at FOCS 1999.
         More emphasis on algorithmic applications.
  3. Finite Metric Spaces - Combinatorics, Geometry and Algorithms by Nati Linial
         Proceedings of the International Congress of Mathematicians III, 573--586 Beijing, 2002.
     
     

• Workshops and Open Problems

  1. Haifa workshop on Discrete metric spaces.
         List of open problems from the workshop
  2. Princeton workshop
         The follow-up workshop just concluded.
     
     

• Embeddings into Euclidean and l₁ spaces

      Upper bounds:
  

  1. J. Bourgain. On {Lipschitz} embeddings of finite metric spaces in {Hilbert} space. Israel J. of Math. 1985.
         How to embed any n-point metric into any l_p space with distortion O(log n)
  2. N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica (1995) 15, pp. 215-245.
         Algorithmic version of Bourgain's embedding, many other embeddings results.
  3. S. Rao. Small distortion and volume preserving embeddings for Planar and {Euclidean} metrics, SoCG 1999.
         Planar graphs can be embedded into Euclidean space with distortion sqrt(log n)
  4. A. Gupta, I. Newman, Yu. Rabinovich, A. Sinclair. Cuts, trees and {$\ell_1$}-embeddings of graphs, FOCS 1999.
         Shows that series-parallel graphs embed into l1 with distortion O(1)
  5. C. Chekuri, A. Gupta, I. Newman, Yu. Rabinovich, A. Sinclair. Embedding $k$-outerplanar graphs into $\ell_1$, SODA 2003.
         k-outerplanar graphs embed into l1 with distortion exp(k).

   

  1. D. Shmoys. Approximation algorithms for Cut problems and their application to divide-and-conquer. 1997.
         Approximation algorithms for graph partitioning using embeddings.

      Lower bounds:
  

  1. J. Matousek, On embedding expanders into $l\sb p$ spaces, Israel Journal of Math, 1997.
         Expanders suffer (log n)/p distortion when embedded into Lp spaces
  2. I. Newman, Y. Rabinovich. A lower bound on the distortion of embedding planar metrics into Euclidean space, SoCG 2001.
         Simple planar graphs have large distortions into Euclidean space.
  3. J.R. Lee, A. Naor. Embedding the diamond graph in Lp and dimension reduction in L1. Manuscript.
         A short proof of the [NR01] result.
  4. N. Alon. 
         A lower bound for L2 embeddability.
     
     
• Embeddings into distributions of trees
  
  
  1. N. Alon, R. Karp, D. Peleg, D. B. West, A graph-theoretic game and its application to the k-server problem, SICOMP 1995.
         The paper that introduced the idea of embedding into distributions of trees.
  2. Y. Bartal, Probabilistic Approximations of Metric Spaces and its Algorithmic Applications, FOCS 1996.
         Gives a O(log² n) approximation for metrics by tree distributions, shows that graph decompositions give embeddings.
             He has another paper [Bartal 1998] that improves things to O(log n loglog n). A bit advanced, so 
             read the following  paper instead:
  3. J. Fakcharoenphol, S. Rao and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics. STOC 2003.
         A simple algorithm that gets the tight O(log n) result for all graphs.
  4. G. Konjevod, R. Ravi and F.S. Salman. On approximating planar metrics by tree metrics. IPL 2001.
         O(log n) for planar graphs, lower bounds of Omega(log n) for the grid.
         [GNRS99] above gives a different lower bound for series-parallel graphs.
  5. M. Charikar, C. Chekuri, S. Guha, A. Goel, S. Plotkin. Approximating a Finite Metric by a Small Number of Tree Metrics. FOCS 98.
         How to derandomize Bartal's embeddings, via a "dual" problem.

      Applications of random tree embeddings:

  1. N. Garg, G. Konjevod, R.Ravi. A polylogarithmic approximation algorithm for the group {Steiner} tree problem, SODA 98.
         Reduce the problem to trees, and then solve the resulting (non-trivial) problem.
  2. B. Awerbuch and Y.Azar. Buy-at-Bulk Network Design. FOCS 97.
         Reduce the network design problem to trees, where it is very simple.
  3. 
     
     
• Dimension Reduction
  
  
  1. W. Johnson, J. Lindenstauss. Extensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics 1984.
         Any n-point Euclidean space embeds into O(log n/x²) space with (1+ x) 
         distortion. In fact, a random such subspace will do.
  2. S. Dasgupta, A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss, Random Structures Algorithms, 2002.
         Chernoff-type proof of [JL84]
  3. D. Achlioptas. Database Friendly Random Projections, PoDS 2000.
         How to do [JL84] with unbiased coins. 

   

  1. S. Dasgupta, Learning Mixtures of Gaussians, FOCS 1999.
         Using dimension reduction for learning.
  2. R. Arriaga, S. Vempala. An algorithmic theory of learning: robust concepts and random projection. FOCS 1999.
         Using dimension reduction for learning.
  3. P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, FOCS 2000.
         Unified view of dim. redn.as studying stable distributions, using it for streaming.

   

  1. J. Kleinberg, Two Algorithms for Nearest-Neighbor Search in High Dimensions, STOC 1997.
         Random projection for near-neighbour searching.
  2. P. Indyk, R. Motwani. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. STOC 1998.
         More approx NN searching; uses projections + "point location in equal balls"
  3. E. Kushilevitz and R. Ostrovsky and Y. Rabani. Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. STOC 1998.
         A form of dimension reduction for the hypercube, and using it for NN searching.
  4. More papers on near-neighbour searching can be found in this list.
     
     
• Other Embeddings
  
  
      Spanners:
  
  1. I. Althofer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. D&CG 1993.
         Finding sparse subgraphs that maintain all pair distances.
         Used, e.g., in the network design paper [MP98]
  2. S. Khuller, B. Raghavachari, and N.E. Young. Balancing minimum spanning and shortest path trees, Algorithmica, 1995.
         Finds trees that are simultaneously near-MST and near-shortest path trees
         Used, e.g., in the network design paper [SCRS97]
  3. M. Thorup, U.Zwick. Approximate distance oracles. STOC 2001.
         Gives tree covers: a small set of subtrees such that each shortest-path is maintained by one of them.
         Used, e.g., in network routing paper [TZ02]
  4. A. Gupta, A. Kumar, R. Rastogi. Traveling with a Pez dispenser. FOCS 2001.
         Good tree covers for planar graphs, and using them for routing.
     
     
  1. Y. Rabinovich, R. Raz. Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs. D&CG 99.
         Lower bounds on spanners. Shows: the n-cycle cannot be approximated by a tree.
  2. A. Gupta. Steiner nodes in Trees don't (really) help. SODA 2001.
         Shows a simpler proof of the non-embeddability of the cycle + other results.
  3. K. V. M. Naidu, H. Ramesh. Lower Bounds for Embedding Graphs into Graphs of Smaller Characteristic. FST&TCS 2002.
         Better lower bounds on spanners.
     

      Volume Respecting Embeddings:
  

  1. U. Feige. Approximating the bandwidth via volume respecting embeddings. STOC 1998.
         How to maintain not only pair-wise distances, but also "volumes" of sets of points.
         Used for laying out graphs on the integers with small stretch (but arbitrary contraction).

      Additive Approximations to Metrics:
  

  1. R.Agarwala, V. Bafna, M. Farach, M. Paterson, M.Thorup. On the Approximability of Numerical Taxonomy. SICOMP 1999.
         Fitting distances by tree metrics.
  2. J. Hastad, L. Ivansson, J. Lagergren. Fitting points on the real line and applications to RH mapping. J. Algorithms.
         Fitting distances by line metrics.

      Metric Property Testing:
  

  1. M. Parnas, D. Ron: Testing metric properties. STOC 2001.
         Testing in sublinear time whether a metric has some claimed properties.
  2. R. Krauthgamer, O. Sasson. Property testing of data dimensionality. SODA 2003.
         Further results in that vein.

      Growth Restrictions on Metrics:
  

  1. A. Gupta, R. Krauthgamer and J.R. Lee. Bounded geometries, fractals, and low-distortion embeddings. FOCS 2003
         Properties of metrics which cannot grow very fast.
  2. D. Karger, M. Ruhl. Finding nearest neighbors in growth-restricted metrics. STOC 2002.
         Using growth restrictions to improve NN searches in graphs.

      Metric Labeling:
  

  1. J. Kleinberg, É.Tardos. Approximation algorithms for classification problems. FOCS 1999.
         Map a graph into a set of labels to minimize the average stretch + assignment costs.
         Uses results from tree embeddings.

      Ramsay Properties of Metrics:
  

  1. Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Metric Ramsey-Type Phenomena. STOC 2003.
         Every metric has a large subspace that is close to Euclidean.

Last updated: 12/01/2003