# minimize absolute value

Suppose we have $n$ real numbers $a_1, a_2, \ldots, a_n$. We know that the solution which minimizes $$\sum_{i=1}^n |x-a_i|$$ is $x^*=$ median of $a_1, a_2\ldots, a_n$.

Now suppose that we should choose $k<n$ numbers, namely $x^*_1, x^*_2, \ldots, x^*_k$ which corresponds to the $a_i$'s. For example $x^*_1$ corresponds to $a_1$ and $a_2$; $x^*_2$ corresponds to $a_3$, $a_4$ and $a_5$ etc. which minimizes $$|x^*_1-a_1| + |x^*_1-a_2| + |x^*_2-a_3|+ x^*_2-a_4|+ |x^*_2-a_5|+ \ldots + |x^*_k-a_n|$$

Let me give a more concrete example:

Suppose we have 2,4,5,11,14 and $k=2$. Thus we need to choose $x_1$ and $x_2$. If we choose $x_1=5$ and associate it to 2,4 and 5; $x_2=11$ and associate it to 11 and 14 we get $$|2-5|+|4-5|+|5-5|+|11-11|+|14-11|=3+1+3=7$$

The question is how we can choose such $x_k$'s and how we should associate them to $a_i$'s. Is there any algorithm?

-
Sounds like you are asking for algorithms for K-means clustering. Does the standard algorithm section in above wiki page help? – achille hui Feb 8 '13 at 0:51
@achillehui: Thanks, that is what I have been looking for. – neticin Feb 8 '13 at 2:25
– barto Apr 4 '15 at 9:12

If you break your sum into multiple sums, one for each $x_k$, you see that each $x_k$ affects only one sum, and each sum depends on only $x_k$. Therefore, to minimize the overall total, you minimize each individual sum. Therefore, $x_k$ should be the median of the $a_i$ corresponding to it.
How can I choose the $a_i$ corresponding to $x_k$? – neticin Feb 7 '13 at 23:45
You said in the problem that you had $X_k$ corresponding to certain $a_i$'s. If it isn't just given as part of the problem, then I do not understand the problem set up. – Aaron Feb 8 '13 at 5:52