Consider a set of $n$ correlated random variables, $A =\{X_1, \ldots, X_n\}$. Suppose that I have another set, $B$, of all possible combinations of size $k$ of the random variables. Now, if for each combination in $B$ I summed the variables, I would have $C(n, k)$ new variables. Of all these new variables, surely one has the smallest and one has the largest variance. With minimum number of operations, I would like to find which $k$ elements of $A$ result in the smallest and largest variance when they are summed.
For uncorrelated variables this is pretty easy, since the variance of the sum is simply the sum of variances, i.e.: $\operatorname{Var}\Big(\sum_{i=1}^n X_i\Big) = \sum_{i=1}^n \operatorname{Var}(X_i)$
In that case, the sum of $k$ smallest and largest variables in $A$ that have the smallest and largest variances, give the smallest and largest variances when they are summed. However, when the variables are correlated the pairwise correlation between the variables complicates things.
$\operatorname{Var}\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n \sum_{j=1}^n \operatorname{Cov}(X_i, X_j) = \sum_{i=1}^n \operatorname{Var}(X_i) + 2\sum_{1\le i}\sum_{<j\le n}\operatorname{Cov}(X_i,X_j)$
Here is an example:
Let $A = \{X_1, X_2, X_3, X_4\}$ and $k = 2$.
$B = \{ \{X_1, X_2\}$ , $\{X_1, X_3\}$ , $\{X_1, X_4\}$, $\{X_2, X_3\}$, $\{X_2, X_4\}$, $\{X_3,X_4\}\}$
So we would have C(4,2) = 6 sums, i.e., $\{Y_1, Y_2, Y_3, Y_4, Y_5, Y_6\}$ where:
$Y_1 = X_1+X_2$ ; $Y_2 = X_1+X_3$ ; $Y_3 = X_1+X_4$ ; $Y_4 = X_2+X_3$ ; $Y_5 = X_2+X_4$ ; $Y_6 = X_3+X_4$
Given that $\operatorname{Var}(Y_3) < \operatorname{Var}(Y_1) < \operatorname{Var}(Y_2) < \operatorname{Var}(Y_6) < \operatorname{Var}(Y_4) < \operatorname{Var}(Y_5)$, I am interested in $Y_3$ and $Y_5$, since they have the smallest and largest variances. My question is whether there is an efficient way like the uncorrelated case to find $Y_3$ and $Y_5$ by only looking at $A$?
By efficient I mean polynomial time or better.