# Choosing a subset of binary variables to maximize the sum of the highest $K$

Consider the following problem:

Input:

• 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?

Example:
Input:

• $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.