# Is there any known result for 1-median problem with negative weights in Euclidean space?

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.

• Hi Jian ! can you provide a link for the statement that "the problem has been considered in graphs" ? Feb 23, 2014 at 5:42
• – jian
Feb 24, 2014 at 6:32
• thanks. added them inline. It sounds like an interesting open problem. Feb 24, 2014 at 6:58
• hmmm, I think we need some sort of constraints or more info: Consider the case where all weights are negative.
– usul
Feb 25, 2014 at 17:20
• It would be great if the algorithm can tell us whether the solution is unbounded (like some linear programming algorithm).
– jian
Feb 27, 2014 at 13:27