Name
Abstract | ||
|---|---|---|
Motivated by applications in combinatorial optimization, we study the extent to which the global properties of a metric space, and especially its embeddability into $\ell_1$ with low distortion, are determined by the properties of its small subspaces. We establish both upper and lower bounds on the distortion of embedding locally constrained metrics into various target spaces. Other aspects of locally constrained metrics are studied as well, in particular, how far are those metrics from general metrics. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/090780304 | Symposium on Discrete Algorithms |
Keywords | DocType | Volume |
small subspaces,metric space,general metrics,metric spaces,global property,local versus global properties,low distortion,lower bound,combinatorial optimization,various target space,dimension reduction | Journal | 41 |
Issue | ISSN | ISBN |
1 | 0097-5397 | 0-89871-605-5 |
Citations | PageRank | References |
10 | 0.82 | 21 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjeev Arora | 1 | 4508 | 379.31 |
| László Lovász | 2 | 2640 | 881.45 |
| Ilan Newman | 3 | 1149 | 82.18 |
| Yuval Rabani | 4 | 2265 | 274.98 |
| Yuri Rabinovich | 5 | 36 | 3.90 |
| Santosh Vempala | 6 | 3546 | 523.21 |