Hardness of a special case of maximum matching

Question

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?

Welcome to MSE! It really helps readability to format questions using MathJax (see FAQ). SOme of this write up could use cleanup to make it look and read better. Regards — Amzoti, May 25 '13 at 02:32

score 1 · Answer 1 · answered May 27 '13 at 01:41

1

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.

answered May 27 '13 at 01:41

Hans Engler

15,439

Link outdated above – root-11 Nov 29 '14 at 17:58

score 0 · Answer 2 · answered Nov 29 '14 at 17:58

0

This is a case of the weapons-target assignment problem: http://en.wikipedia.org/wiki/Weapon_target_assignment_problem

answered Nov 29 '14 at 17:58

root-11

61

Hardness of a special case of maximum matching

2 Answers2