text: In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced our understanding of finite metrics, but has also resulted in many algorithmic applications. However, we still do not understand the interaction between various graph-theoretic (topological) properties of graphs, and the doubling (geometric) properties of the shortest-path metrics induced by them. For instance, the following natural question suggests itself: graph @math with @math such that the shortest path metric @math on @math is still doubling, and which agrees with @math on @math . This is often useful, given that unweighted graphs are often easier to reason about. We show that for any metric space @math , there is an graph @math with shortest-path metric @math such that -- for all @math , the distances @math , and -- the doubling dimension for @math is not much more than that of @math , where this change depends only on @math and not on the size of the graph. We show a similar result when both @math and @math are restricted to be trees: this gives a simpler proof that doubling trees embed into constant dimensional Euclidean space with constant distortion. We also show that our results are tight in terms of the tradeoff between distortion and dimension blowup.
  @cite_6: It is proved that ifY ⊂X are metric spaces withY havingn≧2 points then any mapf fromY into a Banach spaceZ can be extended to a map ( f ) fromX intoZ so that ( | f |_ lip c log n | f |_ lip ) wherec is an absolute constant. A related result is obtained for the case whereX is assumed to be a finite-dimensional normed space andY is an arbitrary subset ofX.
  @cite_24: Given a graph G = (V, E), a set of terminals T ⊆ V, and a metric D on T, the 0-extension problem is to assign vertices in V to terminals, so that the sum, over all edges e, of the distance (under D) between the terminals to which the end points of e are assigned, is minimized. This problem was first studied by Karzanov. Calinescu, Karloff and Rabani gave an O(logk) approximation algorithm based on a linear programming relaxation for the problem, where k is the number of terminals. We improve on this bound, and give an O(log k log log k) approximation algorithm for the problem.
  @cite_23: 
  @cite_5: In the 0-extension problem, we are given a weighted graph with some nodes marked as terminals and a semimetric on the set of terminals. Our goal is to assign the rest of the nodes to terminals so as to minimize the sum, over all edges, of the product of the edge's weight and the distance between the terminals to which its endpoints are assigned. This problem generalizes the multiway cut problem of [SIAM J. Comput. , 23 (1994), pp. 864--894] and is closely related to the metric labeling problem introduced by Kleinberg and Tardos [Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science, New York, 1999, pp. 14--23]. We present approximation algorithms for 0-Extension . In arbitrary graphs, we present a O(log k)-approximation algorithm, k being the number of terminals. We also give O(1)-approximation guarantees for weighted planar graphs. Our results are based on a natural metric relaxation of the problem previously considered by Karzanov [European J. Combin., 19 (1998), pp. 71--101]. It is similar in flavor to the linear programming relaxation of Garg, Vazirani, and Yannakakis [SIAM J. Comput. , 25 (1996), pp. 235--251] for the multicut problem, and similar to relaxations for other graph partitioning problems. We prove that the integrality ratio of the metric relaxation is at least @math for a positive c for infinitely many k. Our results improve some of the results of Kleinberg and Tardos, and they further our understanding on how to use metric relaxations.
  @cite_13: LetH=(T,U) be a connected graph,V?Ta set, andca non-negative function on the unordered pairs of elements ofV. In theminimum0-extension problem(*), one is asked to minimize the inner productcmover all metricsmonVsuch that (i)mcoincides with the distance function ofHwithinT; and (ii) eachv?Vis at zero distance from somes?T, i.e.m(v,s)=0. This problem is known to be NP-hard ifH=K3(as being equivalent to the minimum 3-terminal cut problem), while it is polynomially solvable ifH=K2(the minimum cut problem) orH=K2,r(the minimum (2,r)-metric problem). We study problem (*) for all fixedH. More precisely, we consider the linear programming relaxation (**) of (*) that is obtained by dropping condition (ii) above, and callHminimizableif the minima in (*) and (**) coincide for allVandc. Note that for such anHproblem (*) is solvable in strongly polynomial time. Our main theorem asserts thatHis minimizable if and only ifHis bipartite, has no isometric circuit with six or more nodes, and is orientable in the sense thatHcan be oriented so that nonadjacent edges of any 4-circuit are oppositely directed along this circuit. The proof is based on a combinatorial and topological study of tight and extreme extensions of graph metrics. Based on the idea of the proof of the NP-hardness for the minimum 3-terminal cut problem in 4, we then show that the minimum 0-extension problem is strongly NP-hard for many non-minimizable graphsH. Other results are also presented.
  @cite_11: A metric space X is said to be absolutely Lipschitz extendable if every Lipschitz function f from X into any Banach space Z can be extended to any containing space Y⊇X, where the loss in the Lipschitz constant in the extension is independent of Y,Z, and f. We show that various classes of natural metric spaces are absolutely Lipschitz extendable. To cite this article: J.R. Lee, A. Naor, C. R. Acad. Sci. Paris, Ser. I 338 (2004).
summary: Somewhat similar in spirit to our work is the @math -extension problem @cite_13 @cite_5 @cite_24 . Given a graph @math , the 0-extension ( cf. Lipschitz Extendability @cite_6 @cite_23 @cite_11 ) problem deals with extending a (Euclidean) embedding of the vertices of the graph to an embedding of the convex closure of the graph, while approximately preserving the Lipschitz constant of the embedding. Our results can be interpreted as analogues to the above where the goal is to approximately preserve the doubling dimension.