Let $S=\{1,\ldots,n\}$ be a set and $w_i (\geq 0)$ be the weight of element $i$. Let $R_j, j = 1,\ldots,m$ be subsets of $S$, called the restriction sets. Choose elements from set $S$ to maximize total weights such that at most one element is selected from each set $R_j$. This problem can be modeled as $\max \sum_i w_ix_i$ subject to $\sum\limits_{i\in R_j}x_i \leq 1$ for all $j$ and $x_i \in \{0,1\}$.

I think this problem is well-known in literature but I have no idea what it is. Does anyone know this problem and the algorithm to solve it. Thanks

  • $\begingroup$ It's clearly an instance of an integer linear program. I doubt you can do much better. $\endgroup$ – quasi Jan 29 '18 at 10:45
  • $\begingroup$ The problem is closely related to the maximum weight clique problem, which is notoriously hard to approximate well, let alone solve exactly, in the worst case. In practical applications, there is often some structure that can be exploited, though. $\endgroup$ – Taneli Huuskonen Jan 29 '18 at 11:12

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.