Deterministic metric $1$-median selection with very few queries

Abstract

Given an $n$-point metric space $(M,d)$, {\sc metric $1$-median} asks for a point $p\in M$ minimizing ${\sum }_{x\in M}d(p,x)$. We show that for each computable function $f:{\mathbb{Z}}^{+}\to {\mathbb{Z}}^{+}$ satisfying $f(n)=\omega (1)$, {\sc metric $1$-median} has a deterministic, $o(n)$-query, $o(f(n)\cdot \log n)$-approximation and nonadaptive algorithm. Previously, no deterministic $o(n)$-query $o(n)$-approximation algorithms are known for {\sc metric $1$-median}. On the negative side, we prove each deterministic $O(n)$-query algorithm for {\sc metric $1$-median} to be not $(\delta \log n)$-approximate for a sufficiently small constant $\delta >0$. We also refute the existence of deterministic $o(n)$-query $O(\log n)$-approximation algorithms.

Part of this paper appears in {\em Proceedings of the 27th International Computing and Combinatorics Conference} (COCOON 2021)