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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.