Computer Science – Data Structures and Algorithms
Scientific paper
2010-02-18
Computer Science
Data Structures and Algorithms
previous revision was the wrong file: the new revision: changed (extended considerably) the treatment of finite volumes (see r
Scientific paper
We introduce and study finite $d$-volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define $\ell_1$-volumes and show that they contain Euclidean volumes and hypertree volumes. We show that they can approximate any $d$-volume with $O(n^d)$ multiplicative distortion. On the other hand, contrary to Bourgain's theorem for $d=1$, there exists a $2$-volume that on $n$ vertices that cannot be approximated by any $\ell_1$-volume with distortion smaller than $\tilde{\Omega}(n^{1/5})$. We further address the problem of $\ell_1$-dimension reduction in the context of $\ell_1$ volumes, and show that this phenomenon does occur, although not to the same striking degree as it does for Euclidean metrics and volumes. In particular, we show that any $\ell_1$ metric on $n$ points can be $(1+ \epsilon)$-approximated by a sum of $O(n/\epsilon^2)$ cut metrics, improving over the best previously known bound of $O(n \log n)$ due to Schechtman. In order to deal with dimension reduction, we extend the techniques and ideas introduced by Karger and Bencz{\'u}r, and Spielman et al.~in the context of graph Sparsification, and develop general methods with a wide range of applications.
Newman Ilan
Rabinovich Yuri
No associations
LandOfFree
Finite Volume Spaces and Sparsification does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Finite Volume Spaces and Sparsification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finite Volume Spaces and Sparsification will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-406194