Approximate Greedy Clustering and Distance Selection for Graph Metrics

摘要: $\newcommand{\eps}{\varepsilon}$ In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms approximation schemes for these inputs given as graph shortest path metrics or high-dimensional Euclidean metrics. The first of is the greedy permutation (or farthest-first traversal) a space: points space in which each point far possible from all previous points. We describe randomized to find $(1+\eps)$-approximate permutations any with $n$ vertices $m$ edges expected time $O(\eps^{-1}(m+n)\log n\log(n/\eps))$, spaces $O(\eps^{-2} n^{1+1/(1+\eps)^2 + o(1)})$. Additionally deterministic algorithm exact treewidth $O(1)$ worst-case $O(n^{3/2}\log^{O(1)} n)$. second distance selection: $k \in [ \binom{n}{2} ]$, are interested computing $k$th smallest space. show that planar one can approximate distance, up constant factor, near linear time.