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

Abstract

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 $o(n^{1+1/(h-1)})$-query $(2h-\Omega (1))$-approximation algorithms for any constant $h\in {\mathbb{Z}}^{+}\setminus \{1\}$.

References in corpus (2)

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