<blockquote>
  <p>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.</p>
</blockquote>

<p>Is there any known result for this problem. It seems the problem has been considered in graphs (<a href="http://rutcor.rutgers.edu/~do99/EA/ECela.ps" rel="nofollow">one</a>, <a href="http://link.springer.com/article/10.1007/s10878-008-9187-4" rel="nofollow">two</a>). What about in $R^d$ ?  Due to the negative weights, the problem is not convex any more.</p>

CC BY-SA 3.0
2014-02-23T05:42:00.000Z
Hi Jian ! can you provide a link for the statement that "the problem has been considered in graphs" ?
Suresh Venkat
CC BY-SA 3.0
2014-02-24T06:32:13.770Z
Here are two examples: http://rutcor.rutgers.edu/~do99/EA/ECela.ps  http://link.springer.com/article/10.1007%2Fs10878-008-9187-4
jian
CC BY-SA 3.0
2014-02-24T06:58:34.677Z
thanks. added them inline. It sounds like an interesting open problem.
Suresh Venkat
CC BY-SA 3.0
2014-02-25T17:20:39.857Z
hmmm, I think we need some sort of constraints or more info: Consider the case where all weights are negative.
usul
CC BY-SA 3.0
2014-02-27T13:27:07.470Z
It would be great if the algorithm can tell us whether the solution is unbounded (like some linear programming algorithm).
jian
CC BY-SA 3.0
2017-05-05T16:34:04.647Z
The way the problem statement is written, $p$ does not necessarily have to be one of $\nu_1 \ldots \nu_n$ (so it looks like a 'mean' problem rather than a 'median' problem) ?
Andre Holzner
<ds.algorithms><cg.comp-geom>
Is there any known result for 1-median problem with negative weights in Euclidean space?
jian
# Is there any known result for 1-median problem with negative weights in Euclidean space?

(Asked by: username_0 on 2014-02-23)

> 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](http://rutcor.rutgers.edu/~do99/EA/ECela.ps), [two](http://link.springer.com/article/10.1007/s10878-008-9187-4)). What about in $R^d$ ? Due to the negative weights, the problem is not convex any more.

**Tags:** ds.algorithms, cg.comp-geom

> **Comments:**
> **username_1**: Hi Jian ! can you provide a link for the statement that "the problem has been considered in graphs" ?  
> **username_0**: Here are two examples: http://rutcor.rutgers.edu/~do99/EA/ECela.ps  http://link.springer.com/article/10.1007%2Fs10878-008-9187-4  
> **username_1**: thanks. added them inline. It sounds like an interesting open problem.  
> **username_2**: hmmm, I think we need some sort of constraints or more info: Consider the case where all weights are negative.  
> **username_0**: It would be great if the algorithm can tell us whether the solution is unbounded (like some linear programming algorithm).  
> **username_3**: The way the problem statement is written, $p$ does not necessarily have to be one of $\nu_1 \ldots \nu_n$ (so it looks like a 'mean' problem rather than a 'median' problem) ?  

---

## 0 answers

