A lower bound for metric 1-median selection
classification
💻 cs.DS
keywords
metricproblemalgorithmsapproximationaverageboundconsiderdeterministic
read the original 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.
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.