  Recommendation systems aim to identify items that are likely to be of
interest to users. In many cases, users are interested in package
recommendations as collections of items. For example, a dietitian may wish to
derive a dietary plan as a collection of recipes that is nutritionally
balanced, and a travel agent may want to produce a vacation package as a
coordinated collection of travel and hotel reservations. Recent work has
explored extending recommendation systems to support packages of items. These
systems need to solve complex combinatorial problems, enforcing various
properties and constraints defined on sets of items. Introducing constraints on
packages makes recommendation queries harder to evaluate, but also harder to
express: Queries that are under-specified produce too many answers, whereas
queries that are over-specified frequently miss interesting solutions.
  In this paper, we study query relaxation techniques that target package
recommendation systems. Our work offers three key insights: First, even when
the original query result is not empty, relaxing constraints can produce
preferable solutions. Second, a solution due to relaxation can only be
preferred if it improves some property specified by the query. Third,
relaxation should not treat all constraints as equals: some constraints are
more important to the users than others. Our contributions are threefold: (a)
we define the problem of deriving package recommendations through query
relaxation, (b) we design and experimentally evaluate heuristics that relax
query constraints to derive interesting packages, and (c) we present a crowd
study that evaluates the sensitivity of real users to different kinds of
constraints and demonstrates that query relaxation is a powerful tool in
diversifying package recommendations.
