# A problem solved by weighted median

Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily in ascending orders) and associated weights $w_1,w_2,\ldots,w_n$ such that $\sum_{i=1}^n w_i = 1$. The objective is to find a point $p$ on the straight line such that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum, where $x_p$ is the $x$-coordinate of $p$.

Prove that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum at a point $p$, where $p$ is such that $\sum_{x_i<x_p} w_i < \frac{1}{2}$ and $\sum_{x_i>x_p} w_i \leq \frac{1}{2}$.

I am trying to use algorithm Select to prove it. The algorithm divides the x-coordinates into $[n/5]$ sublists such that first $[n/5]-1$ sublists contain exactly 5 elements each, while the remaining one contains $n \pmod 5$ elements. Then we find the median of each sublist. Repeat the same process for each sublist.

But I think I get the gist of the problem, I think it is sufficient to prove that if $q$ is any point on the line such that $q≠p$,then $\sum_{i=1}^n|x_q-x_i| w_i≥\sum_{i=1}^n|x_p- x_i | w_i$, where $x_q$ is the x-coordinate of $q$.

But I am going no where with this. Am I using the wrong approach? Should I be using algorithm Min to get this? If yes, can someone explain how to get it?

• What have you tried? Where did you get stuck? You need to prove something; what proof methods have you considered? We don't want to just do your exercise for you; we want to help you understand. However, as you haven't given us much to work with, it's hard to know how to help you. 1. Can you solve any special cases? e.g., where the weights are all equal? Have you tried working through some examples? 2. Have you tried using calculus? If you take the derivative, what do you know about what the value of the derivate should be at the minimum point? – D.W. Feb 29 '16 at 17:56
• 3. Algorithms are irrelevant here, as the exercise doesn't ask you to find an algorithm. – D.W. Feb 29 '16 at 17:56

Let $I = \{ i : x_i < x_p \}$ and $J = \{ j : x_j > x_p \}$. Then the derivative of your objective function with respect to $x_p$ is $$\sum_{i \in I} w_i - \sum_{j \in J} w_j.$$