Small distortion and volume preserving embeddings for Planar and Euclidean metrics Sat&h Rao NEC Research Institute 4 Independence Way Princeton. NJ 08540 Abstract A finite metric space, (S,d) , contains a finite set of points and a distance function on pairs of points. A contraction is an embedding, h, of a finite met- ric space (S, d) into Rd where for any u, v E S, the Euclidean (&) distance between h(u) and h(v) is no more than d(u, v). The distortion of the embedding is the maximum over pairs of the ratio of d(u, w) and the Euclidean distance between h(u) and h(v). Bourgain showed that any graphical metric could be embedded with distortion O(logn). Linial, Lon- don and Rabinovich and Aumman and Rabani used such embeddings to prove an O(log k) approximate max-flow min-cut theorem for k commodity flow problems. A generalization of embeddings that preserve dis- tances between pairs-of points are embeddings that preserve volumes of larger sets. In particular, A (k, c)-volume respecting embedding of n-points in any metric space is a contraction where every subset of k points has within an ck-’ factor of its maximal possible k - l-dimensional volume. Feige invented these embeddings in devising a polylogarithmic approximation algorithm for the bandwidth problem using these embeddings. Feige’s methods have subsequently been used by Vempala for approximating versions of the VLSI layout problem. Feise showed that a (k, O(10,g~‘~ n,/m)) vol- ume r&ecting embedding‘ eksted.” Be -recently found improved (k, 0( mdk log k + log n)) vol- ume respecting embeddings. For metrics arising from planar graphs (planar metrics), we give (k,O(m)) volume respecting contractions. As a corollary, we give embeddings for Permission to makkr digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. XC’99 Miami Beach Florida Copyright ACM 1999 I-581 13-068-6/99/06...$5.00 planar metrics with distortion O(e). This gives rise to an O(e)-approximate max-flow min-cut theorem for multicommodity flow problems in planar graphs. We also give an improved bound for volume re- specting embeddings for Euclidean metrics. In par- ticular, we give an (k,O(dog klog D)) volume re- specting embedding where D is the ratio of the largest distance to the smallest distance in the met- ric. Our results give improvements for Feige’s and Vempala’s approximation algorithms for planar and Euclidean metrics. For volume respecting embed- dings, our embeddings do not degrade very fast when preserving the volumes of large subsets. This may be useful in the future for approximation algorithms or if volume .respecting embeddings prove to be of inde- pendent interest. 1 Introduction A finite metric space, (S,d) , contains a finite set of points and a distance function on pairs of points. A contraction is an embedding, h, of a finite met- ric space (S,d) into Rd where for any u, u E S, the Euclidean (es) distance between h(u) and h(v) is no more than d(~, w). The distortion of the embedding is the maximum over pairs of the ratio of d(u, v) and the Euclidean distance between h(u) and h(v). Bourgain showed that any graphical metric could be embedded with distortion O(logn). Linial, Lon- don and Rabinovich and Aumman and Rabani used such embeddings to prove an O(log k) approximate max-flow min-cut theorem for k commodity flow problems. A generalization of embeddings that preserve dis- tances between pairs of points are embeddings that preserve volumes of larger sets. In particular, A (k, c)-volume respecting embedding of n-points in any metric space is a contraction where every subset of k points has within an ck-’ factor of its maximal 300possible k - l-dimensional volume. Feige invented these embeddings in devising a polylogarithmic approximation algorithm for the bandwidth problem using these embeddings. Feige’s methods have subsequently been used by Vempala for approximating versions of the VLSI layout problem. Feige showed that a (k, O(log3/2 ndm)) vol- ume respecting embedding existed. He recently found improved (k, O(-& log k + log n)) vol- ume respecting embeddings. 1.1 Results For metrics .arising from planar graphs (planar met- rics), we give (k, 0( fi)) volume respecting con- tractions. As a corollary, we give embeddings for planar metrics with distortion O(m). As a corol- lary, we give embeddings for planar graphical met- rics with distortion O(&). Combining this re- sult with arguments of Linial, London, and Rabi- novich and Aumann and Rabani [9, 11, we obtain an O(-)-approximate max flow min cut theorem for multicommodity flow problems in planar graphs. The previous bound of O(logn) was first derived for grids in 1983 by Karp, et.al. [7], and for general planar graphs in 1993 [8]. In 1994, general graphs were shown to have O(log k)-max flow min-cut the- orems for k-commodity flow problems 19, l]. There are numerous results for finding exact max flow min- cut theorems for special cases of the multicommodity flow problem in planar graphs. See, for example, the survey by Frank [6]. We also give an improved bound for volume re- specting embeddings for Euclidean metrics. In par- ticular, we give an (k, O(&og klog D)) volume re- specting embedding ‘wheie c is the I I ratio of the largest distance to the smallest distance in the met- ric. Our Euclidean metric result leads to (k, log3’2 nm) volume respecting embeddings for general graphs. This follows