Optimal collective dichotomous choice under partial order constraints

Ruth Ben-Yashar*, Samir Khuller, Sarit Kraus

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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 accepted when certain others are rejected. We show that this type renders the choice problem to be NP-complete by reduction from the problem of Vertex Cover. Applicability of the generalization to information filtering is discussed.

Original languageEnglish (US)
Pages (from-to)349-364
Number of pages16
JournalMathematical social sciences
Volume41
Issue number3
DOIs
StatePublished - May 2001

Keywords

  • Constraints
  • D70
  • D81
  • Information filtering
  • Optimal collective dichotomous choice

ASJC Scopus subject areas

  • Sociology and Political Science
  • Social Sciences(all)
  • Psychology(all)
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Optimal collective dichotomous choice under partial order constraints'. Together they form a unique fingerprint.

Cite this