Concrete/theoritical center of a cluster in a general metric space

What i call center is the point which minimize the distance to every points of a specific cluster.

From what i know we can look for a concrete point in the cluster get an approximation of the center.

For any space with a metric $$d$$, look for point which minimize the sum of distance to all others points

$$argmin_{x \in Cluster}(\sum_{x_i \in Cluster}{d(x, x_i}))$$

Unfortunately this approach has a $$O(n^2)$$ cost.

I'm sure that this problem is a common one but i didn't succeed to find something and i would be happy to know :

• Cool references
• The complexity of this problem in the general context
• If some sweet heuristic exist to find an approximate concrete or not point satisfying the problem in less than $$O(n^2)$$.
• "In a euclidean space $\mathcal R^d$, the center is the mean obtained in $O(n)$". Wrong. The point that minimize the distance to 3 given points is the circumcenter of those 3 points. Feb 18, 2019 at 10:58
• "In a hamming space $\{0, 1\}^d$, the center is the majority vote obtained in $O(n)$" Can you add a reference in the question? Feb 18, 2019 at 11:02
• The best algorithm depends on the metric. Do you have a fixed, particular metric that you want an algorithm for? If so, what is your metric? Or do you want an algorithm that works for any metric? If so, how is the metric specified or provided to the algorithm? As an oracle (a black-box function the algorithm can invoke on any pair of points of its choosing)? Are we guaranteed that the metric satisfies any extra properties, beyond being a distance metric?
– D.W.
Feb 18, 2019 at 20:29
• If the metric is specified as an oracle, I suspect you might be able to demonstrate that you can't do better than $O(n^2)$; e.g., that you'll have to compute the distance between every pair of points, or something. (If you want to look for such a proof, I'd look for some kind of adversarial argument: if there is any pair of points whose distance you haven't queried, see if you can make the algorithm's answer wrong by making that distance be very large or very small.)
– D.W.
Feb 18, 2019 at 20:29