David Eppstein,
Sariel Har-Peled, and
Anastasios Sidiropoulos.
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 find $(1+\eps)$-approximate greedy permutations of
any graph with $n$ vertices and $m$ edges in expected time
$O\pth{\eps^{-1}(m+n)\log n\log(n/\eps)}$, and to find
$(1+\eps)$-approximate greedy permutations of points in
high-dimensional Euclidean spaces in expected time
$O(\eps^{-2} n^{1+1/(1+\eps)^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 of the
two problems we consider is distance selection: given
$k \in \IntRange{ \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.
PDF.
Last modified: Mon Jul 6 13:05:52 CDT 2015