A lower bound for metric 1-median selection

Abstract

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.

Cited by in corpus (3)

• A deterministic sublinear-time nonadaptive algorithm for metric $1$-median selection
• A Las Vegas approximation algorithm for metric $1$-median selection
• Metric $1$-median selection: Query complexity vs. approximation ratio