A lower bound for metric 1-median selection
Chang, Ching-Lueh
Original · EN
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²)-query (4-Ω(1))-approximation algorithms.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.