PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
This is a special instance of the “metric embedding” problem. Recall that a metric space is a collection of points with a distance function d(x,y) satisfying d(x,x) = 0, d(x,y) = d(y,x), and d(x,y) <= d(x,z) + d(z,y) for any points x,y,z in the metric. The shortest-paths-in-a-graph distance is a metric as is the Euclidean distance in any d-dimensional Euclidean space. A well-studied problem is how well we can embed one metric space in another. Here, an embedding from a metric X to a metric Y is simply a mapping of the points in X to the points in Y. The quantity L/K in the problem is called the “distortion” of the embedding.
An important result is that any metric on n points can be embedded in some Euclidean space of dimension d with distortion L/K where d*L/K = O(log^2 n). More specifically, one can obtain distortion O(log n) in O(log n)-dimensional space. There are graphs (constant-degree expanders) whose shortest-path metric has distortion Omega(log n) with any embedding into Euclidean space of any dimension. Furthermore, these graphs cannot be embedded into o(log^2 n)-dimensional space with constant distortion, so these results are essentially tight. The algorithm for finding such an embedding is actually quite simple and can be easily implemented in polynomial time. Strictly speaking, it is a randomized algorithm and the expected distortion is O(log n), but a deterministic variant can be developed. The interested reader is referred to 1 and 2 . In particular, theorem 3.1 in 1 contains many useful and interesting facts regarding embedding a finite metric into more structured spaces.
- J. Bourgain, “On Lipschitz embedding of finite metric spaces in Hilbert space”, Israel J. Math, 52, 1985, p. 46-52.
- N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications”, Combinatorica, 15(2), 1995, p. 215-245.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here