Metric 1-Median Selection: Query Complexity vs. Approximation Ratio

DOI10.1007/978-3-319-42634-1_11zbMath1425.68139arXiv1509.05662OpenAlexW2777770977MaRDI QIDQ2817856

Ching-Lueh Chang

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

Mathematics Subject Classification ID

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)

A lower bound for metric 1-median selection

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