Publication
Title
On the complexity of package recommendation problems
Author
Abstract
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.
Language
English
Source (journal)
SIAM journal on computing. - Philadelphia, Pa, 1972, currens
Publication
Philadelphia, Pa : 2013
ISSN
0097-5397
Volume/pages
42:5(2013), p. 1940-1986
ISI
000328889100007
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 06.02.2014
Last edited 23.06.2017
To cite this reference