Some results on approximate 1-median selection in metric spaces

A 1-median in a finite metric space is a point with the minimum average distance to all other points. Given a positive integer n and oracle access to a distance metric on {1,2,…,n}, we study the problem of finding a 1-median. In particular, we show the nonexistence of (1) deterministic O(1)-approximation o(n)-query algorithms, (2) deterministic (2−Ω(1))-approximation o(n2)-query algorithms for graph metrics, (3) deterministic (3−Ω(1))-approximation o(n2)-query algorithms and (4) Monte-Carlo (2−Ω(1))-approximation o(n)-query algorithms with an Ω(1) probability of success. We also show a Monte-Carlo (2+ϵ)-approximation O((log2(1/ϵ))/ϵ3)-query algorithm with a 1−O(ϵ) probability of success, where ϵ∈(0,1).