A lower bound for metric 1-median selection
From MaRDI portal
Publication:340556
DOI10.1016/j.jcss.2016.08.004zbMath1353.68111arXiv1401.2195OpenAlexW2400041466MaRDI QIDQ340556
Publication date: 14 November 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1401.2195
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Some results on approximate 1-median selection in metric spaces
- A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
- Optimal time bounds for approximate clustering
- Randomized query processing in robot path planning
- A 1.488 approximation algorithm for the uncapacitated facility location problem
- Deterministic sublinear-time approximations for metric 1-median selection
- On approximating metric 1-median in sublinear time
- Approximating $k$-Median via Pseudo-Approximation
- Metric 1-Median Selection: Query Complexity vs. Approximation Ratio
- Sublinear time algorithms for metric space problems
- A Simple D 2-Sampling Based PTAS for k-Means and other Clustering Problems
- Approximating average parameters of graphs
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- Linear-time approximation schemes for clustering problems in any dimensions
- A new greedy approach for facility location problems
- Local Search Heuristics for k-Median and Facility Location Problems
- Fast Approximation of Centrality
- A Lower Bound for the Complexity of Monotone Graph Properties
This page was built for publication: A lower bound for metric 1-median selection
