Geometry/Functional Analysis
Absolute Lipschitz extendability
Comptes Rendus. Mathématique, Volume 338 (2004) no. 11, pp. 859-862.

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 YX, 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.

On dit qu'un espace métrique X a la propriété d'extension lipschitzienne absolue si pour tout espace de Banach Z, toute fonction lipschitzienne f de X dans Z peut être étendue à tout espace métrique Y contenant X, avec une perte dans la constante de Lipschitz de l'extension qui ne dépend pas du choix de Y,Z et f. Nous montrons que plusieurs classes naturelles d'espaces métriques ont la propriété d'extension lipschitzienne absolue.

Published online:
DOI: 10.1016/j.crma.2004.03.005
Lee, James R. 1; Naor, Assar 2

1 Computer Science Division, University of California at Berkeley, Berkeley, CA 94720, USA
2 Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA
     author = {Lee, James R. and Naor, Assar},
     title = {Absolute {Lipschitz} extendability},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {859--862},
     publisher = {Elsevier},
     volume = {338},
     number = {11},
     year = {2004},
     doi = {10.1016/j.crma.2004.03.005},
     language = {en},
     url = {}
AU  - Lee, James R.
AU  - Naor, Assar
TI  - Absolute Lipschitz extendability
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 859
EP  - 862
VL  - 338
IS  - 11
PB  - Elsevier
UR  -
DO  - 10.1016/j.crma.2004.03.005
LA  - en
ID  - CRMATH_2004__338_11_859_0
ER  - 
%0 Journal Article
%A Lee, James R.
%A Naor, Assar
%T Absolute Lipschitz extendability
%J Comptes Rendus. Mathématique
%D 2004
%P 859-862
%V 338
%N 11
%I Elsevier
%R 10.1016/j.crma.2004.03.005
%G en
%F CRMATH_2004__338_11_859_0
Lee, James R.; Naor, Assar. Absolute Lipschitz extendability. Comptes Rendus. Mathématique, Volume 338 (2004) no. 11, pp. 859-862. doi : 10.1016/j.crma.2004.03.005.

[1] Bartal, Y. Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium Foundations of Computer Science, 1998

[2] Benyamini, Y.; Lindenstrauss, J. Geometric Nonlinear Functional Analysis. vol. 1, Amer. Math. Soc. Colloq. Publ., vol. 48, American Mathematical Society, Providence, RI, 2000

[3] Calinescu, G.; Karloff, H.; Rabani, Y. Approximation algorithms for the 0-extension problem, Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, 2001

[4] Fakcharoenphol, J.; Harrelson, C.; Rao, S.; Talwar, K. An improved approximation algorithm for the 0-extension problem, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, 2003

[5] J. Fakcharoenphol, S. Rao, K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, in: 35th Annual ACM Symposium on Theory of Computing, ACM, 2003, in press

[6] A. Gutpa, R. Krauthgamer, J.R. Lee, Bounded geometries, fractals, and low-distortion embeddings, in: Proceedings of the 44th Annual Symposium on Foundations of Computer Science, 2003, in press

[7] Johnson, W.B.; Lindenstrauss, J.; Schechtman, G. Extensions of Lipschitz maps into Banach spaces, Israel J. Math., Volume 54 (1986) no. 2, pp. 129-138

[8] Kirszbraun, M.D. Über die zusammenziehenden und Lipschitzchen Transformationen, Fund. Math. (1934) no. 22, pp. 77-108

[9] Klein, P.; Plotkin, S.A.; Rao, S. Excluded minors, network decomposition, and multicommodity flow, 25th Annual ACM Symposium on Theory of Computing, May 1993, pp. 682-690

[10] J.R. Lee, A. Naor, Extending Lipschitz functions via random metric partitions, Preprint

[11] Linial, N.; Saks, M. Low diameter graph decompositions, Combinatorica, Volume 13 (1993) no. 4, pp. 441-454

[12] Matoušek, J. Extension of Lipschitz mappings on metric trees, Comment. Math. Univ. Carolin., Volume 31 (1990) no. 1, pp. 99-104

[13] Mohar, B.; Thomassen, C. Graphs on Surfaces, Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 2001

[14] Rao, S. Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the 15th Annual Symposium on Computational Geometry, ACM, 1999, pp. 300-306

[15] Robertson, N.; Seymour, P.D. Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B, Volume 48 (1990) no. 2, pp. 255-288

[16] Wells, J.H.; Williams, L.R. Embeddings and Extensions in Analysis, Ergeb. Math. Grenzgeb., vol. 84, Springer-Verlag, New York, 1975

Cited by Sources: