On ultrametric $1$-median selection
Ching-Lueh Chang · arXiv (Cornell University) · 2019
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/ε))/ε^3)$-time $(1+ε)$-approximation algorithm for all $ε>0$.