Most Popular Package Design and NP-Hard Problem

Abstract

Given a set of items, and a set of user preferences, we investigate the problem of designing a most popular package (or say, a pattern), i.e., a subset of items that maximizes the number of satisfied users. It is a typical problem of data mining. In this paper, we address this issue and propose an efficient algorithm for solving the problem based on a graph structure, called a p*-graph, used to represent the preference of a user, by which a lot of useless checks can be avoided. The time complexity of the algorithm is bounded by O(n²m³), where m is the number of items (or say, attributes) and n is the number of user preferences. Since the problem is essentially NP-hard, the algorithm discussed in this chapter in fact provides a proof of P = NP . CCS Concepts: \(\bullet\) Theory of computation \(\to\) Minimum satisfiability problem.