Maxim Binshtok
Department of Computer Science
Ben-Gurion University
email: maximbi@cs.bgu.ac.il
Ronen I. Brafman
Department of Computer Science
Ben-Gurion University
email: brafman@cs.bgu.ac.il
Soloman E. Shimony
Department of Computer Science
Ben-Gurion University
email: shimony@cs.bgu.ac.il
Ajay Martin
Department of Computer Science
Stanford University
email: ajaym@cs.stanford.edu
Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
Various tasks in decision making and decision support require
selecting a preferred subset of items from a given set of feasible
items. Recent work in this area considered methods for
specifying such preferences based on the attribute values of
individual elements within the set. Of these, the approach
of (Brafman et al. 2006) appears to be the most general. In
this paper, we consider the problem of computing an optimal
subset given such a specification. The problem is shown to
be NP-hard in the general case, necessitating heuristic search
methods. We consider two algorithm classes for this problem:
direct set construction, and implicit enumeration as solutions
to appropriate CSPs. New algorithms are presented in each
class and compared empirically against previous results.
To appear, AAAI-2007
Return to List of Papers