On the Complexity of Package Recommendation Problems

Recommendation systems aim to recommend items that are likely to be of interest to users. This paper investigates several issues fundamental to such systems: (1) We model recommendation systems for packages (sets) of items. We use queries to specify multicriteria for item selections and express compatibility constraints on items in a package, and use functions to compute the cost and usefulness of items to a user. (2) We study recommendations of points of interest to suggest top-$k$ packages. We also investigate recommendations of top-$k$ items as a special case. (3) We identify several problems to decide whether a set of packages makes a top-$k$ recommendation and whether a rating bound is maximum for selecting top-$k$ packages. We also study function problems for computing top-$k$ packages, and counting problems to find how many packages meet the user's criteria. (4) We establish the upper and lower bounds of these problems, all matching, for combined and data complexity. These results reveal the impact of variable sizes of packages, the presence of compatibility constraints, and a variety of query languages for specifying selection criteria and compatibility constraints on the analyses of these problems.