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.

Note: The question has been asked before on MathOverflow(link). But it does not contain any correct answer even in the comments.

  • 2
    $\begingroup$ This sounds a bit like the Sum-of-Square-Roots problem. You may want to take a look at this answer to a previous question: cstheory.stackexchange.com/questions/79/… $\endgroup$ – Michael Lampis Mar 10 at 21:11
  • $\begingroup$ 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 $\endgroup$ – D.W. Mar 10 at 22:49
  • $\begingroup$ @D.W.: If you look at the corresponding decision problem, you may use the standard RAM model of computation. NP-hardness of this problem is unclear (to me). $\endgroup$ – Gamow Mar 11 at 10:02
  • $\begingroup$ I don't think the problem is NP-hard for any real-world scenario. "but they only find an approximate solution for the problem" -> they run in polynomial time in the number of bits you want to find, and they can find these bits exactly. It's unclear to me what exactly your desired output is from the algorithm if this is not sufficient. $\endgroup$ – orlp Mar 11 at 21:44
  • 1
    $\begingroup$ Another way of saying the same as above, is that the approximation algorithms are fast enough, that to all practical purposes the problem can be solved "good enough" in polynomial time. BTW, it is physically solvable in constant time, assuming ideal physics scenario (the same is true for Euclidean TSP). $\endgroup$ – Sariel Har-Peled Mar 17 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.