Comptes Rendus
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

James R. Lee 1; Assar Naor 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 = {James R. Lee and Assar Naor},
     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},
AU  - James R. Lee
AU  - Assar Naor
TI  - Absolute Lipschitz extendability
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 859
EP  - 862
VL  - 338
IS  - 11
PB  - Elsevier
DO  - 10.1016/j.crma.2004.03.005
LA  - en
ID  - CRMATH_2004__338_11_859_0
ER  - 
%0 Journal Article
%A James R. Lee
%A Assar Naor
%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
James R. Lee; Assar Naor. Absolute Lipschitz extendability. Comptes Rendus. Mathématique, Volume 338 (2004) no. 11, pp. 859-862. doi : 10.1016/j.crma.2004.03.005.

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

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

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

[4] J. Fakcharoenphol; C. Harrelson; S. Rao; K. Talwar 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] W.B. Johnson; J. Lindenstrauss; G. Schechtman Extensions of Lipschitz maps into Banach spaces, Israel J. Math., Volume 54 (1986) no. 2, pp. 129-138

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

[9] P. Klein; S.A. Plotkin; S. Rao 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] N. Linial; M. Saks Low diameter graph decompositions, Combinatorica, Volume 13 (1993) no. 4, pp. 441-454

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

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

[14] S. Rao 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] N. Robertson; P.D. Seymour Graph minors. VIII. A Kuratowski theorem for general surfaces, J. Combin. Theory Ser. B, Volume 48 (1990) no. 2, pp. 255-288

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

Cited by Sources:

Comments - Policy