SODA Outtakes: Approximation algorithms for metric embeddings.

One of the most exciting areas of algorithms in the past ten years has been the study of metric embeddings. Given two metric spaces, can we "embed" one in the other (which basically means construct an 1-1 map from points in the first to points in the second) so that distances are roughly preserved ? The seminal paper of Linial, London and Rabinovich demonstrated how to use a low-distortion embedding of a metric space into l₁, to determine a good approximation algorithm for the sparsest cut problem (the distortion of the embedding is the approximation ratio achieved).

This set off a flurry of research into questions of the form "What is the best distortion for embedding spaces of type A into spaces of type B". There is no way I can survey all the results in this area; a new CRC book chapter by Indyk and Matoušek should be able to cover most of the terrain, and the excellent book by Deza and Laurent has much of the technical background. Everything started (in a sense) from the result by Bourgain that any metric space can be embedded into l₁ with distortion O(log n) (albeit in log² n dimensions).

Other questions that were studied along the way:

• what is the minimum distortion that one must face when embedding A into B (metrics derived from expanders proved to be useful gadgets in this regard)
• Can one reduce the dimensionality of a space without distorting distances too much ? This question has numerous implications for all kinds of problems in clustering, data mining, database search, you name it...
• Are there general subclasses of metrics that have low-distortion embeddings ? A fundamental open question here involves metrics on planar graphs. It is still open as to whether they can be embedded in l1 with constant distortion (again, this has implications for sparsest cut in planar graphs)
• Metric "Ramsey theory": if I can't embed the entire metric space, can I embed a large fraction of the points/edges with smaller distortion ? Yair Bartal just gave a nice talk at AT&T on partial embeddings (the "edge" variant).
  

A set of questions that is now getting more attention is the "natural " approximation angle. Although we know that any metric can be embedded in an l_p space with distortion log n, what about a particular metric given to us ? Might one not be able to do better ? And can we come up with an algorithm to determine the BEST distortion for this particular metric ?

It was shown early on that one can find the optimal distortion into l₂ (upto additive error) in polynomial time using semi-definite programming. For l₁, the corresponding question is NP-hard. What I have been seeing is a slew of interesting recent papers that explore hardness results and approximation algorithms for embedding problems:

• Kenyon/Rabani/Sinclair (STOC 2004): They consider bijections between two n-point metric spaces, and present a constant factor approximation in the case when the metrics are derived from a line (as long as OPT is small).
  
• Papadimitriou/Safra (SODA 2005): They show that the minimum distortion bijection between two 3D point sets is hard to approximate to within a factor of 3.
  
• Badoiu, Dhamdhere, Gupta, Rabinovich, Raecke, Ravi, and Sidiropoulos (SODA 2005): A collection of results on embedding metrics in 1D and 2D. One main result is an O(sqrt{n})-approximation for embedding a metric on the line.
  
• Badoiu, Chuzhoy, Indyk, Sidiropoulos (STOC 2005): I don't have a copy of the paper, but the title is indicative enough: "Low-Distortion Embeddings of General Metrics Into the Line"

This is not to say that these problems have not been studied earlier. As far back as 1993 for example, Farach-Colton, Kannan and Warnow had looked at embedding a metric into an ultrametric. However, the current focus on such problems is an interesting new direction in the theory of metric embeddings.

---

p.s usual disclaimers apply: this is a blog post, not a survey, and hence is opinionated and far from comprehensive. Pointers to relevant add ons are welcome.