On the Complexity of Package Recommendation Problems

Ting Deng, Wenfei Fan, Floris Geerts

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)1940-1986
Number of pages57
JournalSIAM Journal on Computing
Issue number5
Publication statusPublished - 2013


Dive into the research topics of 'On the Complexity of Package Recommendation Problems'. Together they form a unique fingerprint.

Cite this