  There has been significant recent interest in the area of group
recommendations, where, given groups of users of a recommender system, one
wants to recommend top-k items to a group that maximize the satisfaction of the
group members, according to a chosen semantics of group satisfaction. Examples
semantics of satisfaction of a recommended itemset to a group include the
so-called least misery (LM) and aggregate voting (AV). We consider the
complementary problem of how to form groups such that the users in the formed
groups are most satisfied with the suggested top-k recommendations. We assume
that the recommendations will be generated according to one of the two group
recommendation semantics - LM or AV. Rather than assuming groups are given, or
rely on ad hoc group formation dynamics, our framework allows a strategic
approach for forming groups of users in order to maximize satisfaction. We show
that the problem is NP-hard to solve optimally under both semantics.
Furthermore, we develop two efficient algorithms for group formation under LM
and show that they achieve bounded absolute error. We develop efficient
heuristic algorithms for group formation under AV. We validate our results and
demonstrate the scalability and effectiveness of our group formation algorithms
on two large real data sets.
