I have a set of N real sequences and need to pick K sequences (with no replacement) such that their sum has the minimum variance.
E.g. I have N=3 real sequences of length 5:
x(1)=[-0.9 0.7 2.0 2.5 1.5] x(2)=[-1.8 -0.2 0.5 -1.3 -0.7] x(3)=[-1.5 -0.9 0.3 1.5 0.4]
If I need to select K=2 sequences, the variance of the sums is:
var(x(1)+x(2))=3.7 var(x(1)+x(3))=6.1 var(x(2)+x(3))=2.5
So I'd want to select sequences 2 & 3.
This is easy to brute force for small N, but my real application has much larger N. For example, for N=20 and K=10, there are 184756 combinations. Since my sequence lengths are long and computational time is critical, this is not feasible.
Is there an efficient algorithm to do the selection? Or even to give an approximate solution? Or reduce the problem space to likely candidates?