Input:
A set of N Users $\{u_1, ..., u_N\}$. A set of M products $\{i_1, ..., i_M\}$.
Every pair $(u,i)$ is associated with the probability of u purchasing the product i, $p_{u,i}$.
Task: Assign each user with exactly $K$ products (notation: $(u,i) \in A$) so that the following objective function is maximized $$ \sum_{i: \exists u \ni (u,i) \in A} \left(1-\prod_{u: (u,i) \in A}{(1-p_{u,i})}\right) $$ Question: Is this problem NP-Hard?
This looks like a version of the "weapon target assignment problem", see e.g. http://web.mit.edu/sloan-msa/Papers/1.5.pdf . It seems that no exact algorithms are known.