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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Hi Jian ! can you provide a link for the statement that "the problem has been considered in graphs" ? $\endgroup$
    – Suresh Venkat
    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$
    – Suresh Venkat
    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

0

Reset to default

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.