Title
On the complexity of package recommendation problems On the complexity of package recommendation problems
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Philadelphia, Pa ,
Subject
Mathematics
Computer. Automation
Source (journal)
SIAM journal on computing. - Philadelphia, Pa, 1972, currens
Volume/pages
42(2013) :5 , p. 1940-1986
ISSN
0097-5397
ISI
000328889100007
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000328889100007&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000328889100007&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000328889100007&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle