Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{w_0, ..., w_m\}$, with $m\leq n$. Our goal will be over the selection of a size $m$ subset $S\subset \boldsymbol{X}$.

Objective: Find

$$ \max_{S} \sum_{i = 0}^m w_i \mathbb{P}\bigg( \sum_{X_j\in S} X_j = i\bigg)$$ $$\text{subject to} |S| = m$$

How can we either compute the optimal solution in polynomial time, or get a constant factor approximation in polynomial time?

Work so far: This problem seems to lend itself to a dynamic program, but the particular method for doing so is not yet clear.

For any $X_j$ that we select, we can somewhat factor out the prior $p_j$ from the sum in the following way $\sum_{i = 0}^m w_i \mathbb{P}\bigg( \sum_{X_j\in S} X_j = i\bigg) = p_j V(X_j =1) + (1-p_j)V(X_j=0)$. Where V is something some previously computed value representing the value we get when $X_j$ is fixed to be 1, or 0 respectively, and we don't yet know the outcomes the other $X_s\in S$. This, in a way, makes the value separable. Here $V$ would give the elements in the table.

To expand on this idea a little further, we could consider the first layer of the table where we would compute $$ p_j w_1 + (1-p_j) w_0$$ for each $1 \leq j\leq n$. Then in the next layer we would have terms of the form $$ \max_{j\neq r}\bigg(p_r\big(p_j w_2 + (1-p_j)w_1\big) + (1-p_r)\big(p_j w_1 + (1-p_j)w_0\big)\bigg) $$ For each $1\leq r\leq n$. We see that the second term $(1-p_r)\big(p_j w_1 + (1-p_j)w_0\big)$ is just a scaler of a value computed in the previous row of our table. However the first term $p_r\big(p_j w_2 + (1-p_j)w_1\big)$ wasn't yet computed, but is similar to our table entry. The difference being that the weights are "shifted up" by 1. That is we have $w_2, w_1$ instead of $w_1, w_0$. We could compute $p_jw_k + (1-p_j)w_{k-1}$ for each $j$ and each $1 \leq k \leq n$ in polynomial time. This "shifting up" of the weights would continue as we went down the table. But it isn't clear if we can compute everything we would need to look up in polynomial time due to this shifting.

Either an optimal solution, or constant factor approximation, are desirable in this situation.

  • $\begingroup$ The optimal solution is likely to be NP-complete as subset selection. So what do you mean by "constant factor approximation" ? Also note that there is no point of having negative $w_i$ as it applies on a unitary vector. I mean you can eventually normalize it to 0, 1. $\endgroup$ – Vince Sep 2 at 12:43
  • $\begingroup$ @Vince By constant factor approximation, I mean, does there exist an algorithm that can give us an $S$ that yields at least $\frac{1}{c}$ of the optimal solution, where $c$ is some constant. Im not sure how it would be NP-complete as a subset selection problem because the subsets depends heavily on one another, it isn't quite like we are electing the maximum from a $2^n$ size list. It feels like we know enough to at least approximate the problem. $\endgroup$ – Barcode Sep 2 at 18:01

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.