# Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, assume $h$ is a fixed integer such that $n \geq h \geq \left \lfloor \frac{n+1}{2} \right \rfloor$ . Consider the following problem: $$\mbox{minimize } \frac{1}{h} \sum_{i=1}^{n}{(w_iv_i)^2} - \left(\frac{1}{h} \sum_{i=1}^{n}{w_iv_i}\right)^2,$$ under the condition that: $$\sum_{i=1}^{n}{w_i} = h.$$

In other words, I am looking for the subset of size $h$ which minimizes the (sample) variance of that subset. I know that I can sort the values $v_i$ and then check every subset of $h$ consecutive values from left to right (it can be shown that the knapsack should contain contiguous elements for this problem). This would lead to a solution in $\mathcal{O}(n\log(n))$ time. I am curious to find out if a faster algorithm can be found (i.e. without a complete sort).

• Do you mean $w_i$'s are the variables to be optimized and others (such as $v_i$'s, $h$, $n$) are fixed parameters? – xskxzr Sep 13 '18 at 11:09
• @xskxzr Precisely! Everything is fixed except for the $w_i$'s. – LuckyStapler Sep 13 '18 at 12:03