A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection
classification
💻 cs.DS
keywords
algorithmdeterministicmedianmetricnonadaptiveselectionapproximationarbitrary
read the original abstract
We give a deterministic $O(hn^{1+1/h})$-time $(2h)$-approximation nonadaptive algorithm for $1$-median selection in $n$-point metric spaces, where $h\in\mathbb{Z}^+\setminus\{1\}$ is arbitrary. Our proof generalizes that of Chang.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.