Metric 1-median selection with fewer queries

Abstract

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. We show that given any $n$-point metric space $(M,d)$, the problem of finding ${\mathrm{argmin}}_{i\in M}{\sum }_{j\in M}d(i,j)$ (breaking ties arbitrarily) has a deterministic, $O(h(n)\cdot n^{1+1/h(n)})$-time, $O(n^{1+1/h(n)})$-query, $(2h(n))$-approximation and nonadaptive algorithm. Our proofs modify those of Chang~\cite{Cha15, Cha15CMCT} with the following improvements: (1) We improve Chang's~\cite{Cha15} query complexity of $O(h(n)\cdot n^{1+1/h(n)})$ to $O(n^{1+1/h(n)})$, everything else being equal. (2) Chang's~\cite{Cha15CMCT} unpublished work establishes our result only when $n$ is a perfect $(h(n))$th power.

A preliminary version of this paper appears in {\em Proceedings of the 2017 IEEE International Conference on Applied System Innovation}, Sapporo, Japan