  Consider the problem of finding a point in a metric space
$(\{1,2,\ldots,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-\Omega(1))$-approximation algorithms for any constant
$h\in\mathbb{Z}^+\setminus\{1\}$.
