On ultrametric $1$-median selection

Abstract

Consider the problem of finding a point in an ultrametric space with the minimum average distance to all points. We give this problem a Monte Carlo $O(({\log }^2(1/\epsilon ))/{\epsilon }^3)$-time $(1+\epsilon )$-approximation algorithm for all $\epsilon >0$.