Centroid in $\ell_2$ distance

Question

Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing $$ argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right) $$

Answer 1

This is the geometric median problem. There is a nearly linear time algorithm based on interior point methods due to Cohen et al.: to find a $(1+\varepsilon)$-approximation their algorithm runs in time $O(nd\log^3(n/\varepsilon))$. Note that some approximation is necessary, because the optimal solution may not be rational and doesn't have to be a simple function of the input. See the paper for references to prior work.