7
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Hi Jian ! can you provide a link for the statement that "the problem has been considered in graphs" ? $\endgroup$ – Suresh Venkat Feb 23 '14 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 '14 at 6:32
  • $\begingroup$ thanks. added them inline. It sounds like an interesting open problem. $\endgroup$ – Suresh Venkat Feb 24 '14 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 '14 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 '14 at 13:27

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.