A lower bound for metric 1-median selection

2014/01/09 by Ching-Lueh Chang, Chang, Ching-Lueh · 1 citation
Business, Management and Accounting · Computer Science · Engineering · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Indoor and Outdoor Localization Technologies

paper · pdf · doi:10.48550/arxiv.1401.2195

openalex publication_date 2014/01/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider the problem of finding a point in an n-point metric space with the minimum average distance to all points. We show that this problem has no deterministic o(n²)-query (4-Ω(1))-approximation algorithms.

Citations

• Local Search Heuristics for k-Median and Facility Location Problems

Cited by

• Metric 1-median selection: Query complexity vs. approximation ratio

Related

• Metric 1-median selection: Query complexity vs. approximation ratio
• A Las Vegas approximation algorithm for metric 1-median selection
• Deterministic metric 1-median selection with very few queries
• On ultrametric 1-median selection
• A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection