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

Abstract

We give a deterministic $O(h{n}^{1+1/h})$-time $(2h)$-approximation nonadaptive algorithm for $1$-median selection in $n$-point metric spaces, where $h\in {\mathbb{Z}}^{+}\setminus \{1\}$ is arbitrary. Our proof generalizes that of Chang.