Deterministic sublinear-time approximations for metric 1-median selection

Given oracle access to an n  -point metric space (M,d)(M,d), let metric 1-median be the problem of finding argminx∈M∑y∈Md(x,y), breaking ties arbitrarily. We show that metric 1-median has a deterministic nonadaptive O(n3/2)O(n3/2)-time 4-approximation algorithm.

► Metric 1-median asks for a point x   in a metric space (M,d)(M,d) minimizing ∑y∈Md(x,y)∑y∈Md(x,y).
► This paper shows that metric 1-median has a deterministic nonadaptive O(n3/2)O(n3/2)-time 4-approximation algorithm.
► Our result, which concerns deterministic algorithms, is not subsumed by that of Indyk (1999, 2000).
► Our result is not subsumed by those of Guha et al. (2003) because our algorithm is nonadaptive and 4-approximate.