Metric 1-median selection with fewer queries

Ching-Lueh Chang

Let $h:{\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}\setminus \{1\}$ be any function such that $h(n)$ and $\lceil n^{1/h(n)}\rceil$ are computable from $n$ in $O(h(n)\cdot n^{1+1/h(n)})$ time. W…