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

2015/09/18 by Ching-Lueh Chang, Chang, Ching-Lueh
Business, Management and Accounting · Computer Science · #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #Facility Location and Emergency Management

paper · pdf · doi:10.48550/arxiv.1509.05662

openalex publication_date 2015/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider the problem of finding a point in a metric space (\1,2,…,n\,d) with the minimum average distance to other points. We show that this problem has no deterministic o(n^1+1/(h-1))-query (2h-Ω(1))-approximation algorithms for any constant h∈ℤ⁺∖\1\.

Citations

• A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
• A lower bound for metric 1-median selection

Related

• A lower bound for metric 1-median selection
• Deterministic metric 1-median selection with very few queries
• Metric 1-median selection with fewer queries
• A Las Vegas approximation algorithm for metric 1-median selection
• A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection