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

Ching-Lueh Chang

Consider the problem of finding a point in a metric space $(\{1,2,\dots ,n\},d)$ with the minimum average distance to other points. We show that this problem has no deterministic $…