On ultrametric $1$-median selection

Ching-Lueh Chang

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+…