Given a set of $n$ points $v_1,\ldots,v_n$ in $R^d$, find a point $p$ such that $\sum_{i=1}^n w_i d(p,v_i)$ is minimized, where $w_i$ is the weight of $v_i$, which may be positive or negative.

Is there any known result for this problem. It seems the problem has been considered in graphs (one, two). What about in $R^d$ ? Due to the negative weights, the problem is not convex any more.

  • $\begingroup$ Hi Jian ! can you provide a link for the statement that "the problem has been considered in graphs" ? $\endgroup$ Feb 23, 2014 at 5:42
  • 1
    $\begingroup$ Here are two examples: rutcor.rutgers.edu/~do99/EA/ECela.ps link.springer.com/article/10.1007%2Fs10878-008-9187-4 $\endgroup$
    – jian
    Feb 24, 2014 at 6:32
  • $\begingroup$ thanks. added them inline. It sounds like an interesting open problem. $\endgroup$ Feb 24, 2014 at 6:58
  • $\begingroup$ hmmm, I think we need some sort of constraints or more info: Consider the case where all weights are negative. $\endgroup$
    – usul
    Feb 25, 2014 at 17:20
  • $\begingroup$ It would be great if the algorithm can tell us whether the solution is unbounded (like some linear programming algorithm). $\endgroup$
    – jian
    Feb 27, 2014 at 13:27


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.