Metric 1-Median Selection: Query Complexity vs. Approximation Ratio
From MaRDI portal
Publication:2817856
DOI10.1007/978-3-319-42634-1_11zbMath1425.68139arXiv1509.05662OpenAlexW2777770977MaRDI QIDQ2817856
Publication date: 2 September 2016
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1509.05662
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) 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
- Deterministic sublinear-time approximations for metric 1-median selection
- On approximating metric 1-median in sublinear time
- Sublinear time algorithms for metric space problems
- A Simple D 2-Sampling Based PTAS for k-Means and other Clustering Problems
- 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
- Local Search Heuristics for k-Median and Facility Location Problems
This page was built for publication: Metric 1-Median Selection: Query Complexity vs. Approximation Ratio