Limitations to Fréchet's metric embedding method (Q2382346): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Set OpenAlex properties.
 
(5 intermediate revisions by 4 users not shown)
Property / author
 
Property / author: Yair Bartal / rank
Normal rank
 
Property / author
 
Property / author: Manor Mendel / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Mikhail I. Ostrovskii / rank
Normal rank
 
Property / author
 
Property / author: Yair Bartal / rank
 
Normal rank
Property / author
 
Property / author: Manor Mendel / rank
 
Normal rank
Property / reviewed by
 
Property / reviewed by: Mikhail I. Ostrovskii / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / arXiv ID
 
Property / arXiv ID: math/0406404 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On metric Ramsey-type phenomena / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4938152 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Lipschitz embedding of finite metric spaces in Hilbert space / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximating the bandwidth via volume respecting embeddings / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3767843 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The geometry of graphs and some of its algorithmic applications / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the distortion required for embedding finite metric spaces into normed spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: On embedding expanders into \(\ell_p\) spaces / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4530626 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On dominated \(\ell_1\) metrics / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximate distance oracles / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2009836834 / rank
 
Normal rank

Latest revision as of 08:41, 30 July 2024

scientific article
Language Label Description Also known as
English
Limitations to Fréchet's metric embedding method
scientific article

    Statements

    Limitations to Fréchet's metric embedding method (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    9 October 2007
    0 references
    The paper is devoted to low-distortion embeddings of finite metric spaces into the Banach spaces \(\ell_p\) \((1\leq p<\infty)\). The distortion of an (injective) embedding \(f:X\to\ell_p\) is defined as the product of the Lipschitz constants \(\text{Lip}(f)\cdot\text{Lip}(f^{-1}|_{f(X)})\). The authors define a Fréchet embedding as an embedding \(f:X\to\ell_p^S\) (\(S\) is the set of all nonempty subsets of \(X\)) given by \[ f(x)=\{\alpha_A\cdot\text{distance}(x,A)\}_{A\in S}, \] where \(\alpha_A\) are some real numbers (usually assumed to be non-negative). Such embeddings play a significant role in the theory [see \textit{J. Bourgain}, Isr. J. Math. 52, 46--52 (1985; Zbl 0657.46013); \textit{S. Rao}, ``Small distortion and volume preserving embeddings for planar and Euclidean metrics'', in: Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), 300--306 (electronic), ACM, New York (1999; Zbl 0993.68504)]. The problem considered in this paper is inspired by the recent studies on Ramsey type problems of the following type: given a finite metric space, a how large subset of it has a small-distortion embedding into \(\ell_2\)? See \textit{M. Mendel} and \textit{A. Naor} [J.~Eur. Math. Soc. 9, No. 2, 253--275 (2007; Zbl 1122.68043)] for an important recent Ramsey type result and references. The point is that in the recent achievements on Ramsey type problems Fréchet embeddings are not used, instead they use approximations of metrics based on hierarchically well-separated trees introduced by \textit{Y. Bartal} [``Probabilistic approximation of metric spaces and its algorithmic applications'', in: 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), 184--193, IEEE Comput. Soc. Press, Los Alamitos, CA (1996)]. The main result of the present paper (Theorem 2) shows that it is not coincidental: some of the known Ramsey type results cannot be achieved using Fréchet embeddings. The presentation of the main result is self-contained. The final section of the paper contains comments on relations between ultrametrics and dominated \(\ell_1\) metrics introduced by \textit{J. Matoušek} and \textit{Y. Rabinovich} [Isr. J. Math. 123, 285--301 (2001; Zbl 0987.46022)].
    0 references
    finite metric space
    0 references
    Lipschitz mapping
    0 references
    low-distortion embedding
    0 references
    Banach space
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references