Given a set of elements, and a set of user preferences (where each preference is a conjunction of positive or negative preferences for individual elements), this research investigates the problem of designing the most “popular package”, i.e., a subset of the elements that maximizes the number of satisfied users. Numerous instances of this problem occur in practice. For example, a vacation package consisting of a subset of all possible activities may need to be assembled, that satisfies as many potential customers as possible, where each potential customer may have expressed his preferences (positive or negative) for certain activities. Likewise, the problem of designing new products, i.e., deciding which features to add to a new product that satisfies as many potential customers as possible, also falls under this framework. The research presents innovative optimal and approximate algorithms, and studies their performance. The experimental evaluation on real and synthetic datasets shows that the proposed optimal and approximate algorithms are efficient for moderate and large datasets respectively.
展开▼
