This paper generalizes optimal collective dichotomous choices by including
constraints which limit combinations of acceptance and rejection decisions
for m projects under consideration. Two types of constraints are examined.
The first type occurs when acceptance of some projects requires acceptance
of others. This type reduces the choice problem to the tractable (solvable
in polynomial time) problem of finding a maximum weight closed subset of a
directed acyclic graph. The second type occurs when some projects must be a
ccepted when certain others are rejected. We show that this type renders th
e choice problem to be NP-complete by reduction from the problem of Vertex
Cover. Applicability of the generalization to information filtering is disc
ussed. (C) 2001 Elsevier Science B.V. All rights reserved.