Given an n -point metric space ( M , d ) , metric 1 -median asks for a point p ∈ M minimizing ∑ x ∈ M d ( p , x ) . We show that for each computable function f : Z + → Z + satisfying f ( n ) = ω ( 1 ) , metric 1 -median has a deterministic, o ( n ) -query, o ( f ( n ) ⋅ log ⁡ n ) -approximation and nonadaptive algorithm. Previously, no deterministic o ( n ) -query o ( n ) -approximation algorithms are known for metric 1 -median . On the negative side, we prove each deterministic O ( n ) -query algorithm for metric 1 -median to be not ( δ log ⁡ n ) -approximate for a sufficiently small constant δ > 0 . We also refute the existence of deterministic o ( n ) -query O ( log ⁡ n ) -approximation algorithms.