Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 4 down vote favorite

I have two versions of the same question:

  1. Given a list of numbers (with possible duplicates), how to find a k-subset (with possible duplicates) that maximize the variance? is there a more efficient way than the obvious "check-all-k-subsets"?
  2. Given a set of numbers, how do I select from that set a list of k numbers that maximize the variance?
share|improve this question
2  
I believe there's a simple $O(k)$ algorithm, because when $k \gt 1$, a variance-maximizing subset must consist of the $k_0$ smallest and $k-k_1$ largest elements, whence a search over $k_0=1,2,\ldots,k-1$ does the trick. – whuber♦ Mar 16 '12 at 19:37
Don't forget about computing the $k$ smallest and largest elements of the input, this requires $O(n \log k)$. – krlmlr Mar 19 '12 at 3:05
Good point, @user. Regardless, these execution times ($O(k)$ for a pre-sorted list and $O(n\log(k))$ otherwise) are very small compared to the number of $k$-subsets of $n$ whenever $k\gt 1$. – whuber♦ Mar 19 '12 at 17:29

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.