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

We give a deterministic O(hn1+1/h)O(hn1+1/h)-time (2h)(2h)-approximation nonadaptive algorithm for 1-median selection in n  -point metric spaces, where h∈Z+∖{1}h∈Z+∖{1} is arbitrary. Our proof generalizes that of Chang [2].