Approximate greedy clustering and distance selection for graph metrics

Abstract

In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms and approximation schemes for these problems on inputs given as graph shortest path metrics or high-dimensional Euclidean metrics. The first of these problems is the greedy permutation (or farthest-first traversal) of a finite metric space: a permutation of the points of the space in which each point is as far as possible from all previous points. We describe randomized algorithms to compute $(1+\varepsilon)$-approximate greedy permutations of any graph with $n$ vertices and $m$ edges in expected time $O\bigl(\varepsilon^{-1}(m+n)\log n\log(n/\varepsilon) \bigr)$. We also present an algorithm that computes a $(1+\varepsilon)$-approximate greedy permutations of points in high-dimensional Euclidean spaces in expected time $O(\varepsilon^{-2} n^{1+1/(1+\varepsilon)^2 + o(1)})$. Additionally we describe a deterministic algorithm to find exact greedy permutations of any graph with $n$ vertices and treewidth $O(1)$ in worst-case time $O(n^{3/2}\log^{O(1)} n)$.

The second problem we consider is distance selection: given $k \le \binom{n}{2}$, we are interested in computing the $k$th smallest distance in the given metric space. We show that for planar graph metrics one can approximate this distance, up to a constant factor, in near linear time.