1

Given $n$ numbers $a_1<a_2<...<a_n$ how would we find a $m$-element subset ($m \leq n$), with the smallest variance? If I knew what the optimal mean for the smallest variance is I could just greedily choose numbers closest to the mean, but how would I find this mean?

I thought about it this way: each mean has to fall between some element of the sequence so we check if we can find $m$ elements closest to $(a_i+a_{i+1})/2$ for $i \in \{1,...,n-1\}$, if we do this sequentially, then we would find our optimal mean.

But that's obviously wrong, can someone point me in the right direction?

Arek Krawczyk
  • 2,114
  • 1
    The $m$ elements of the optimal are going to be consecutive. This is because if you have an $m$ subset that skips some element. You can always include that element into the subset and drop either the smallest or largest element in the subset. This will make the subset to be more packed. – OR. Mar 21 '14 at 18:56
  • 1
    With this, all is needed is to find the $m$ consecutive numbers $a_{i_1}< a_{i_2}<...<a_{i_m}$ such that $a_{i_m}-a_{i_1}$ is minimal. – OR. Mar 21 '14 at 19:00

0 Answers0