Some results on approximate 1-median selection in metric spaces
From MaRDI portal
Publication:418725
DOI10.1016/j.tcs.2011.12.003zbMath1238.68186OpenAlexW2005964087MaRDI QIDQ418725
Publication date: 30 May 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.003
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (5)
A lower bound for metric 1-median selection ⋮ On ultrametric 1-median selection ⋮ On approximating metric 1-median in sublinear time ⋮ Metric 1-Median Selection: Query Complexity vs. Approximation Ratio ⋮ An efficient noisy binary search in graphs via Median approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Matrix multiplication via arithmetic progressions
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- All-pairs nearly 2-approximate shortest paths in \(O(n^2 \text{ polylog } n)\) time
- All pairs shortest paths for graphs with small integer length edges
- On the exponent of all pairs shortest path problem
- All pairs shortest distances for graphs with small integer length edges
- Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models
- The centrality index of a graph
- All-Pairs Small-Stretch Paths
- A faster algorithm for betweenness centrality*
- Sublinear time algorithms for metric space problems
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- Approximating average parameters of graphs
- Linear-time approximation schemes for clustering problems in any dimensions
- Routing betweenness centrality
- Approximate clustering via core-sets
- On coresets for k-means and k-median clustering
- On k-Median clustering in high dimensions
- All-pairs shortest paths for unweighted undirected graphs in o(mn) time
- Faster Approximation of Distances in Graphs
- Fast Approximation of Centrality
- Paths in graphs
- All-Pairs Almost Shortest Paths
- Better Approximation of Betweenness Centrality
- Approximating Betweenness Centrality
- Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Computing almost shortest paths
- CENTRALITY ESTIMATION IN LARGE NETWORKS
This page was built for publication: Some results on approximate 1-median selection in metric spaces
