Last Modified:
2007-03-23.
Notice: Most of the material in this paper library comes from two other courses:
1. Anupam
Gupta and R. Ravi. At
CMU. Algorithmic
Applications of Metric Embeddings.
2. Tim
Roughgarden At Stanford
Metric Embeddings and
Algorithmic Applications
Books
The most comprehensive survey is in Chapter 15
(latest version, 2005) of
Lectures on Discrete Geometry
(Springer, May 2002) by Jiri
Matousek. And the References.
Surveys
Chapter on embeddings in
Handbook of Discrete and Computational Geometry, Jiri Matousek and Piotr Indyk.
Quick reference on many topics.
Survey by Piotr Indyk at FOCS 1999.
More emphasis on algorithmic applications.
Finite Metric Spaces - Combinatorics,
Geometry and Algorithms by Nati Linial
Proceedings of the International Congress of
Mathematicians III, 573--586 Beijing, 2002
Embeddings into Euclidean and l1 spaces
Upper bounds:
- 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)
- 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.
- Aumann/Rabani, An O(log
k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithms,
SIAM Journal of Computing '98.
Upper bounds (of O(log n)) for the
sparsest cut/maximum concurrent flow gap in general graphs with general
demands. Lower bound and Application
[LR99].
- 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)
- 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)
- 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).
- D. Shmoys. Approximation
algorithms for Cut problems and their application to divide-and-conquer.
1997.
Approximation algorithms for graph partitioning
using embeddings.
- Chawla, Gupta, Racke,
Embeddings of Negative-type Metrics and An Improved Approximation to
Generalized Sparsest Cut, SODA 2005
Gives an O(log^{3/4} n)-distortion
embedding of l_2^2 metrics into l_2.
- Arora, Lee, Naor, Euclidean
distortion and the Sparsest Cut, STOC 2005.
O(log n log log n)-distortion
embedding (again, from l_2^2 to l_2)
- A high-level overview of the ALN embedding is given in these
scribe notes from a course of Sanjeev Arora.
Lower bounds:
Embeddings into distributions of trees
- 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.
- Y. Bartal, Probabilistic
Approximations of Metric Spaces and its Algorithmic Applications, FOCS
1996.
Gives a O(log2 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:
- 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.
- 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.
- 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.
- Fakcharoenphol/Rao/Talwar,
Approximating Metrics by
Tree Metrics (survey), SIGACT News 2004.
A short survey on the previous
papers
- E. Halperin and R. Krauthgamer,
Polylogarithmic inapproximability, STOC '03
Some
hardness result of a polylogarithmic approximation ratio for a natural
NP-hard optimization problem.
Spanning trees
Applications of random tree embeddings:
Dimension Reduction
- 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/x2) space with (1+ x)
distortion. In fact, a random such subspace will do.
- S. Dasgupta, A. Gupta. An
elementary proof of a theorem of Johnson and Lindenstrauss, Random
Structures Algorithms, 2002.
Chernoff-type proof of [JL84]
- D. Achlioptas. Database Friendly Random
Projections, PoDS 2000.
How to do [JL84] with unbiased coins.
Impossibility of dimensionality reduction
Other Embeddings
Spanners:
- 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]
- 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]
- 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]
- A. Gupta, A. Kumar, R. Rastogi. Traveling with a Pez dispenser. FOCS 2001.
conference version.
Good tree covers for planar graphs, and using
them for routing.
- 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.
- 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.
- K. V. M. Naidu, H. Ramesh. Lower Bounds
for Embedding Graphs into Graphs of Smaller Characteristic. FST&TCS
2002.
Better lower bounds on spanners.
Doubling metrics and nearest neighbor search.
- Gupta, Krauthgamer, Lee,
Bounded geometries, fractals, and low-distortion embeddings, FOCS
2003.
Tight bounds for
embedding doubling metric into (low-dimensional) normed spaces.
- Krauthgamer, Lee,
Navigating nets: Simple algorithms for proximity search, SODA 2004.
Present a simple deterministic
data structure for maintaining a set
S
of points in a general metric space,
while supporting proximity search (nearest neighbor and range queries)
and updates to S
(insertions and
sdeletions).
- Krauthgamer, Lee, The black-box
complexity of nearest neighbor search, ICALP 2004.
- Har-Peled, Mendel,
Fast Construction of Nets in Low Dimensional Metrics, and Their
Applications, SCG 2005.
Present
a near linear time algorithm for constructing hierarchical nets in
finite
metric spaces with constant doubling dimension.
- Cole, Gottlieb, Searching
Dynamic Point Sets in Spaces with Bounded Doubling Dimension, STOC
2006.
- Talwar, Bypassing the
embedding: algorithms for low dimensional metrics, STOC 2004.
Uniform sparsest cut
- Arora, Rao, Vazirani,
Expander Flows, Geometric Embeddings, and Graph Partitionings,
STOC 2004.
- Section 4 of Lee,
Distance scales, embeddings, and metrics of negative type, SODA
2005.
Measured descent
Volume Respecting Embeddings:
Some
Improvements:
Inapproximability results:
Additive Approximations to Metrics:
Metric Property Testing:
Growth Restrictions on Metrics:
Metric Labeling:
Ramsay Properties of Metrics:
Spreading Metrics:
Scribed Notes
Scribe notes from a CMU
course taught in Fall 2003 by
Anupam Gupta and R. Ravi.