Sublinear time algorithms for metric space problems
From MaRDI portal
Recommendations
- Automata, Languages and Programming
- Estimating the weight of metric minimum spanning trees in sublinear-time
- On approximating metric 1-median in sublinear time
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- Deterministic sublinear-time approximations for metric 1-median selection
Cited in
(58)- The projection median of a set of points
- A sublinear-time approximation scheme for bin packing
- Fast algorithms for approximating distances
- On Las Vegas approximations for metric 1-median selection
- Fast approximations for sums of distances, clustering and the Fermat-Weber problem
- Faster balanced clusterings in high dimension
- An efficient noisy binary search in graphs via Median approximation
- Minimum spanning paths and Hausdorff distance in finite ultrametric spaces
- On random perfect matchings in metric spaces with not-too-large diameters
- On ultrametric 1-median selection
- Probabilistic k-median clustering in data streams
- On approximating metric 1-median in sublinear time
- Deterministic metric 1-median selection with A 1-o(1) fraction of points ignored
- Metric 1-median selection: query complexity vs. approximation ratio
- On the OBDD representation of some graph classes
- Approximate greedy clustering and distance selection for graph metrics
- A lower bound for metric 1-median selection
- Sublinear‐time approximation algorithms for clustering via random sampling
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Approximating average parameters of graphs
- Fast approximation in subspaces by doubling metric decomposition
- Some results on approximate 1-median selection in metric spaces
- Metric violation distance: hardness and approximation
- On Combinatorial Depth Measures
- Sublinear-time Algorithms
- A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
- Seeding with costly network information
- Speeding up spatial approximation search in metric spaces
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- scientific article; zbMATH DE number 5057523 (Why is no real title available?)
- Net and prune: a linear time algorithm for Euclidean distance problems
- Steiner shallow-light trees are exponentially lighter than spanning ones
- Separating Sublinear Time Computations by Approximate Diameter
- Automata, Languages and Programming
- Computing and Combinatorics
- scientific article; zbMATH DE number 7053319 (Why is no real title available?)
- scientific article; zbMATH DE number 7651177 (Why is no real title available?)
- Expanders with respect to Hadamard spaces and random graphs
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- 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
- Approximating the metric TSP in linear time
- Sublinear time approximation of the cost of a metric k-nearest neighbor graph
- Streaming Euclidean MST to a constant factor
- Approximating all-points furthest pairs and maximum spanning trees in metric spaces
- Deterministic metric 1-median selection with very few queries
- Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median
- Finding ultrametric minimum-diameter spanning trees
- Fast approximations and coresets for (k,)-median under dynamic time warping
- Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
- Bi-criteria sublinear time algorithms for clustering with outliers in high dimensions
- A linear-time approximation algorithm for the minimum-length geometric embedding of trees
- Unexpected effects of online no-substitution k-means clustering
- On coresets for fair clustering in metric and Euclidean spaces and their applications
- Approximate k-closest-pairs in large high-dimensional data sets
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Separating sublinear time computations by approximate diameter
- Small space representations for metric min-sum k-clustering and their applications
This page was built for publication: Sublinear time algorithms for metric space problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2819576)
