Consider the following problem:


  • integers $n > m > k$;
  • $n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$;
  • $n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$).

Let $X_1,\dots,X_n$ be $n$ independent random variables with distribution $X_i \sim \text{Bernoulli}(p_i)$ and define $Y_i = r_iX_i$.

Output: a subset $S$ of $[n]$ of size $m$ that maximizes $r_S = \mathbb{E}[Z_S]$, where $Z_S$ is the random variable $Z_S = \max_{T \subseteq S, |T|=k} \sum_{i\in T} Y_i$.

In other words, we want to select $m$ $Y_i$s such that the expected value of the sum of the largest $k$ of them is maximized.

Can this problem be solved in polynomial time?
Or is it NP-hard?
Is there an efficient $\alpha$-approximation algorithm?


  • $n=3, m=2, k=1$
  • $p_1=1.00, p_2=0.10, p_3=0.01$
  • $r_1=2, r_2=11, r_3=100$

Output: the correct output is $S = \{1,3\}$. Why?

  • $r_{\{1,3\}} = 2.98$: if $X_3=1$, then $Z_S=100$ (since $T=\{3\}$ in this case), otherwise $Z_S=2$ (since $T=\{1\}$ in this case), and thus

    $$r_{\{1,3\}} = \Pr[X_3=1] \times 100 + \Pr[X_3=0] \times 2 = 0.01 \times 100 + 0.99 \times 2 = 2.98.$$

  • $r_{\{1,2\}} = 2.9$: if $X_2=1$, then $Z_S=11$, otherwise $Z_S=2$, and thus

    $$r_{\{1,2\}} = 0.1 \times 11 + 0.9 \times 2 = 2.9.$$

I have been working on this for a while now. As the example above demonstrates, the obvious greedy approach of selecting $Y_i$s with largest expectation does not work. I solved the special case of $k=1$ using dynamic programming. But my guess is that the general case is NP-hard.

Note that the value of of $Z_S$ depends on $S$ and the values of $Y_1,\dots,Y_n$: given $S$, the random process is that we randomly pick the values of the $X_1,\dots,X_n$, compute the values of $Y_1,\dots,Y_n$, then based on the values of $Y_1,\dots,Y_n$ we find the set $T$ of size $k$ that maximizes $\sum_{i \in T} Y_i$, and let $Z_S$ be the result (i.e., we let $Z_S$ be the sum of the $k$ largest values from $Y_1,\dots,Y_n$). This is why just choosing the $k$ $Y_i$'s whose expected value is largest does not yield the correct result.


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.