Volume in General Metric Spaces
Identifieur interne : 000390 ( Main/Curation ); précédent : 000389; suivant : 000391Volume in General Metric Spaces
Auteurs : Ittai Abraham ; Yair Bartal [Israël] ; Ofer Neiman [États-Unis] ; J. Schulman [États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.
Abstract
Abstract: A central question in the geometry of finite metric spaces is how well can an arbitrary metric space be “faithfully preserved” by a mapping into Euclidean space. In this paper we present an algorithmic embedding which obtains a new strong measure of faithful preservation: not only does it (approximately) preserve distances between pairs of points, but also the volume of any set of k points. Such embeddings are known as volume preserving embeddings. We provide the first volume preserving embedding that obtains constant average volume distortion for sets of any fixed size. Moreover, our embedding provides constant bounds on all bounded moments of the volume distortion while maintaining the best possible worst-case volume distortion. Feige, in his seminal work on volume preserving embeddings defined the volume of a set S = {v 1, ..., v k } of points in a general metric space: the product of the distances from v i to { v 1, ..., v i − 1 }, normalized by $\frac{1}{(k-1)!}$ , where the ordering of the points is that given by Prim’s minimum spanning tree algorithm. Feige also related this notion to the maximal Euclidean volume that a Lipschitz embedding of S into Euclidean space can achieve. Syntactically this definition is similar to the computation of volume in Euclidean spaces, which however is invariant to the order in which the points are taken. We show that a similar robustness property holds for Feige’s definition: the use of any other order in the product affects volume1/(k − 1) by only a constant factor. Our robustness result is of independent interest as it presents a new competitive analysis for the greedy algorithm on a variant of the online Steiner tree problem where the cost of buying an edge is logarithmic in its length. This robustness property allows us to obtain our results on volume preserving embeddings.
Url:
DOI: 10.1007/978-3-642-15781-3_8
Links toward previous steps (curation, corpus...)
- to stream Main, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000390
Links to Exploration step
ISTEX:7119E53E7C46A1CDFACCC7FD9C2BD49B0CF8E024Curation
No country items
Ittai Abraham<affiliation><mods:affiliation>E-mail: ittaia@microsoft.com</mods:affiliation><wicri:noCountry code="no comma">E-mail: ittaia@microsoft.com</wicri:noCountry></affiliation>Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Volume in General Metric Spaces</title><author><name sortKey="Abraham, Ittai" sort="Abraham, Ittai" uniqKey="Abraham I" first="Ittai" last="Abraham">Ittai Abraham</name><affiliation><mods:affiliation>Microsoft Research</mods:affiliation><wicri:noCountry code="no comma">Microsoft Research</wicri:noCountry></affiliation><affiliation><mods:affiliation>E-mail: ittaia@microsoft.com</mods:affiliation><wicri:noCountry code="no comma">E-mail: ittaia@microsoft.com</wicri:noCountry></affiliation></author><author><name sortKey="Bartal, Yair" sort="Bartal, Yair" uniqKey="Bartal Y" first="Yair" last="Bartal">Yair Bartal</name><affiliation><mods:affiliation>Hebrew University</mods:affiliation><wicri:noCountry code="no comma">Hebrew University</wicri:noCountry></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: yair@cs.huji.ac.il</mods:affiliation><country wicri:rule="url">Israël</country></affiliation></author><author><name sortKey="Neiman, Ofer" sort="Neiman, Ofer" uniqKey="Neiman O" first="Ofer" last="Neiman">Ofer Neiman</name><affiliation><mods:affiliation>Courant Institute of Mathematical Sciences</mods:affiliation><wicri:noCountry code="no comma">Courant Institute of Mathematical Sciences</wicri:noCountry></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: neiman@cims.nyu.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Schulman, J" sort="Schulman, J" uniqKey="Schulman J" first="J." last="Schulman">J. Schulman</name><affiliation><mods:affiliation>Caltech</mods:affiliation><wicri:noCountry code="no comma">Caltech</wicri:noCountry></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: schulman@caltech.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7119E53E7C46A1CDFACCC7FD9C2BD49B0CF8E024</idno><date when="2010" year="2010">2010</date><idno type="doi">10.1007/978-3-642-15781-3_8</idno><idno type="url">https://api.istex.fr/document/7119E53E7C46A1CDFACCC7FD9C2BD49B0CF8E024/fulltext/pdf</idno><idno type="wicri:Area/Main/Corpus">000390</idno><idno type="wicri:Area/Main/Curation">000390</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Volume in General Metric Spaces</title><author><name sortKey="Abraham, Ittai" sort="Abraham, Ittai" uniqKey="Abraham I" first="Ittai" last="Abraham">Ittai Abraham</name><affiliation><mods:affiliation>Microsoft Research</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: ittaia@microsoft.com</mods:affiliation><wicri:noCountry code="no comma">E-mail: ittaia@microsoft.com</wicri:noCountry></affiliation></author><author><name sortKey="Bartal, Yair" sort="Bartal, Yair" uniqKey="Bartal Y" first="Yair" last="Bartal">Yair Bartal</name><affiliation><mods:affiliation>Hebrew University</mods:affiliation></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: yair@cs.huji.ac.il</mods:affiliation><country wicri:rule="url">Israël</country></affiliation></author><author><name sortKey="Neiman, Ofer" sort="Neiman, Ofer" uniqKey="Neiman O" first="Ofer" last="Neiman">Ofer Neiman</name><affiliation><mods:affiliation>Courant Institute of Mathematical Sciences</mods:affiliation></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: neiman@cims.nyu.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Schulman, J" sort="Schulman, J" uniqKey="Schulman J" first="J." last="Schulman">J. Schulman</name><affiliation><mods:affiliation>Caltech</mods:affiliation></affiliation><affiliation wicri:level="1"><mods:affiliation>E-mail: schulman@caltech.edu</mods:affiliation><country wicri:rule="url">États-Unis</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2010</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">7119E53E7C46A1CDFACCC7FD9C2BD49B0CF8E024</idno><idno type="DOI">10.1007/978-3-642-15781-3_8</idno><idno type="ChapterID">8</idno><idno type="ChapterID">Chap8</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A central question in the geometry of finite metric spaces is how well can an arbitrary metric space be “faithfully preserved” by a mapping into Euclidean space. In this paper we present an algorithmic embedding which obtains a new strong measure of faithful preservation: not only does it (approximately) preserve distances between pairs of points, but also the volume of any set of k points. Such embeddings are known as volume preserving embeddings. We provide the first volume preserving embedding that obtains constant average volume distortion for sets of any fixed size. Moreover, our embedding provides constant bounds on all bounded moments of the volume distortion while maintaining the best possible worst-case volume distortion. Feige, in his seminal work on volume preserving embeddings defined the volume of a set S = {v 1, ..., v k } of points in a general metric space: the product of the distances from v i to { v 1, ..., v i − 1 }, normalized by $\frac{1}{(k-1)!}$ , where the ordering of the points is that given by Prim’s minimum spanning tree algorithm. Feige also related this notion to the maximal Euclidean volume that a Lipschitz embedding of S into Euclidean space can achieve. Syntactically this definition is similar to the computation of volume in Euclidean spaces, which however is invariant to the order in which the points are taken. We show that a similar robustness property holds for Feige’s definition: the use of any other order in the product affects volume1/(k − 1) by only a constant factor. Our robustness result is of independent interest as it presents a new competitive analysis for the greedy algorithm on a variant of the online Steiner tree problem where the cost of buying an edge is logarithmic in its length. This robustness property allows us to obtain our results on volume preserving embeddings.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Amerique/explor/CaltechV1/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000390 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 000390 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Amerique
|area= CaltechV1
|flux= Main
|étape= Curation
|type= RBID
|clé= ISTEX:7119E53E7C46A1CDFACCC7FD9C2BD49B0CF8E024
|texte= Volume in General Metric Spaces
}}
| This area was generated with Dilib version V0.6.32. |  |