12
$\begingroup$

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.

$\endgroup$

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.