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?

  • 1
    $\begingroup$ 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? $\endgroup$ – D.W. Feb 29 '16 at 17:56
  • $\begingroup$ 3. Algorithms are irrelevant here, as the exercise doesn't ask you to find an algorithm. $\endgroup$ – D.W. Feb 29 '16 at 17:56

I don't see how using the select algorithm, or indeed any algorithm, is useful here. Instead, try to use the following observation:

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. $$

| cite | improve this answer | |
  • $\begingroup$ Can you explain a little more please. How is this derivative helpful?? $\endgroup$ – Gautam Raj Kollabathula Feb 29 '16 at 17:31
  • 1
    $\begingroup$ The derivative is helpful since the minimum is achieved when the derivative is zero. The rest I leave for you to figure out. I won't answer any more questions. It's your exercise, after all. $\endgroup$ – Yuval Filmus Feb 29 '16 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.