# Is the Fermat-Weber problem $\mathsf{NP}$-hard?

Given a set of $$n$$ points in a Euclidean space, the Fermat-Weber problem asks to find a center that minimizes the sum of distances of points to that center.

There are iterative algorithms known for this problem like Weiszfeld's algorithm and BMM algorithm, but they only find an approximate solution for the problem.

Moreover, no closed form expression is known for this problem yet. Moreover, Chandrajit Bajaj (link) proved that there is no exact algorithm for the problem under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction of kth roots.

I couldn't properly understand this model of computation. However, I want to ask a fairly straightforward question: "Is Fermat-Weber problem $$\mathsf{NP}$$-hard?" or "showing its $$\mathsf{NP}$$-hardness is still an open problem?". To prove $$\mathsf{NP}$$-hardness, it is required to show a reduction from an $$\mathsf{NP}$$-complete problem to this problem. But I could not find any such reduction in the literature. Please help.

• Doyou intend to work in the Blum-Shub-Shale model and the BSS version of NP, e.g., NP$_\mathbb{R}$? Or are you assuming that the points are at integer/rational coordinates and you mean classical NP-hardness? See, e.g., cstheory.stackexchange.com/q/2119/5038