Metric 1-Median Selection
Ching-Lueh Chang · ACM Transactions on Computation Theory · 2017
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) / h )-query 2 h · (1-ϵ))-approximation algorithms for any constant ϵ >0 and any h = h ( n )∈ Z + \ {1} satisfying h = o ( n 1/( h -1) ). Combining our result with existing ones, we determine the best approximation ratio achievable by deterministic O ( n 1+ϵ )-query (respectively, O ( n 1+ϵ )-time) algorithms to be 2⌈ 1/ϵ ⌉, for all constants ϵ ∈ (0,1).