A lower bound for metric 1-median selection

Ching-Lueh Chang

Consider the problem of finding a point in an n-point metric space with the minimum average distance to all points. We show that this problem has no deterministic $o(n^2)$-query $(4-\Omega(1))$-approximation algorithms.

Knowledge Graph



Sign up or login to leave a comment