Sublinear time algorithms for metric space problems

DOI10.1145/301250.301366zbMath1346.68256OpenAlexW2001907516MaRDI QIDQ2819576

Piotr Indyk

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301366

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (34)

Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ On the OBDD representation of some graph classes ⋮ Minimum spanning paths and Hausdorff distance in finite ultrametric spaces ⋮ A lower bound for metric 1-median selection ⋮ On random perfect matchings in metric spaces with not-too-large diameters ⋮ On ultrametric 1-median selection ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Seeding with Costly Network Information ⋮ A family of pairwise multi-marginal optimal transports that define a generalized metric ⋮ On coresets for fair clustering in metric and Euclidean spaces and their applications ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Unnamed Item ⋮ Approximating average parameters of graphs ⋮ Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored ⋮ Approximating the metric TSP in linear time ⋮ On approximating metric 1-median in sublinear time ⋮ On Combinatorial Depth Measures ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ On Las Vegas approximations for metric 1-median selection ⋮ A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Faster balanced clusterings in high dimension ⋮ Sublinear-time Algorithms ⋮ Expanders with respect to Hadamard spaces and random graphs ⋮ Metric 1-Median Selection: Query Complexity vs. Approximation Ratio ⋮ The projection median of a set of points ⋮ A sublinear-time approximation scheme for bin packing ⋮ Sublinear‐time approximation algorithms for clustering via random sampling ⋮ Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ An efficient noisy binary search in graphs via Median approximation ⋮ Approximate \(k\)-closest-pairs in large high-dimensional data sets ⋮ Fast approximations for sums of distances, clustering and the Fermat-Weber problem

This page was built for publication: Sublinear time algorithms for metric space problems