Metric Techniques in Approximation Algorithms
Anupam Gupta
Carnegie Mellon University
Lecture 1: Metric Embeddings and Tree Approximations
Metric spaces arise in many contexts in approximation algorithms: we
often have to solve problems on metric spaces (e.g., the traveling
salesman problem), and in other cases, metric spaces are convenient
relaxations for problems we seek to solve (e.g., graph partitioning).
Many techniques have been developed over the past decade that allow us
to work with metric spaces; these have often been collectively referred
to as "metric embeddings" techniques. An example of such a technique is
a result saying that any metric space is "essentially a tree": more
precisely, any metric on n points can be represented as a set of trees,
while changing distances by at most a factor of $O(log n)$. In this
first lecture, we will prove this result, while introducing many of the
concepts and definitions in metric embeddings and some useful techniques
in graph partitioning.
Topics:
- Metric spaces: definitions and notation
- Distortion and other notions of distances between metrics
- Important classes of metric spaces
- Low diameter decompositions (LDDs)
- Constructions of LDDs
- Bartal's result: Embeddings into trees with distortion $O(log^2 n)$
- FRT's result: Embeddings into trees with distortion $O(log n)$
- Tree covers
- Sparse neighborhood covers
Lecture 2: Embeddings into Geometric Spaces
The most common way of representing a metric is to give a set of points
in real space R^n (of some dimension) and define distances to be some
norm on this space---say, Euclidean distances (l_2), or the Manhattan
distances (l_1), or some other norm. Such embeddings are extremely
useful, since such a geometric representation is easy to store, to
estimate distances between points, and moreover, many algorithms are
known for geometric spaces. In this lecture, we will survey a set of
techniques to embed metric spaces into these geometric spaces.
Topics:
- Geometric spaces: definitions
- Frechet maps and embeddings into l_infinity
- Bourgain's embedding into l_p spaces
- A matching lower bound due to Matousek
- Rao's embedding into l_2 using LDDs
- Lower bounds
- Embeddings for special classes of graphs
- Measured Descent and other techniques for geometric embeddings.
Lecture 3: The Dimension of Metric Spaces
Geometric metrics have a natural notion of dimension: namely, the
dimension of the ambient space they reside in. However, algorithms tend
to have a poor dependence on the dimension of the space --- this is
often called "the curse of dimensionality". How can we get reduce the
dimension of point sets without changing distances by much? A result of
Johnson and Lindenstrauss shows that any set of n points in Euclidean
space is "close" to an O(log n) dimensional metric space. What other
metric spaces have dimension reduction technqiues, and is this result
the best possible? On another front, this notion of dimension depends on
the representation: can we get a "intrinsic" notion of dimension
independent of the representation?
Topics:
- Geometric and other notions of dimension
- The Johnson-Lindenstrauss result for Euclidean spaces
- Matching lower bounds
- Embeddings of l_2 into l_1
- Impossibility of dimension reduction in l_1 spaces
- Dimension of general metric spaces
- Doubling Dimension
- Construction of sparse spanners, near-neighbor searching
- Other notions of dimension
- Low-dimensional embeddings beyond JL.