Approximate greedy clustering and distance selection for graph metrics

DOI10.20382/JOCG.V11I1A25zbMATH Open1497.68509arXiv1507.01555OpenAlexW4295363783MaRDI QIDQ3387276FDOQ3387276

Authors: David Eppstein, Anastasios Sidiropoulos, Sariel Har-Peled 

Publication date: 12 January 2021

Abstract: $ewcommandepsvarepsilon$ 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(ep{s}^{-1}(m+n)lognlog(n/eps))$, and to find $(1+eps)$-approximate greedy permutations of points in high-dimensional Euclidean spaces in expected time $O(ep{s}^{-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}lo{g}^{O(1)}n)$. The second of the two problems we consider is distance selection: given $$, 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.

Full work available at URL: https://arxiv.org/abs/1507.01555

Recommendations

• Sublinear time algorithms for metric space problems
• Computing the greedy spanner in near-quadratic time
• Computing the greedy spanner in linear space
• Approximating nearest neighbor distances
• Computing the Greedy Spanner in Near-Quadratic Time

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Metric spaces, metrizability (54E35) Computational aspects of digital topology (68U03)

Cited In (6)

• High-dimensional approximate \(r\)-nets
• Near-neighbor preserving dimension reduction via coverings for doubling subsets of \(\ell_1\)
• Approximation algorithms for polynomial-expansion and low-density graphs
• Greedy permutations and Finite Voronoi diagrams (media exposition)
• Title not available (Why is that?)
• Metric-Constrained Optimization for Graph Clustering Algorithms

This page was built for publication: Approximate greedy clustering and distance selection for graph metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387276)