×

On approximating the average distance between points. (English) Zbl 1171.68862

Charikar, Moses (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 10th international workshop, APPROX 2007, and 11th international workshop, RANDOM 2007, Princeton, NJ, USA, August 20–22, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74207-4/pbk). Lecture Notes in Computer Science 4627, 296-310 (2007).
Summary: We consider the problem of approximating the average distance between pairs of points in a high-dimensional Euclidean space, and more generally in any metric space. We consider two algorithmic approaches:
1. Referring only to Euclidean Spaces, we randomly reduce the high-dimensional problem to a one-dimensional problem, which can be solved in time that is almost-linear in the number of points. The resulting algorithm is somewhat better than a related algorithm that can be obtained by using the known randomized embedding of Euclidean Spaces into \(\ell _{1}\)-metric.
2. An alternative approach consists of selecting a random sample of pairs of points and outputting the average distance between these pairs. It turns out that, for any metric space, it suffices to use a sample of size that is linear in the number of points. Our analysis of this method is somewhat simpler and better than the known analysis of Indyk (STOC, 1999). We also study the existence of corresponding deterministic algorithms, presenting both positive and negative results. In particular, in the Euclidean case, this approach outperforms the first approach.
In general, the second approach seems superior to the first approach.
For the entire collection see [Zbl 1123.68005].

MSC:

68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI