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.