hide
Free keywords:
-
Abstract:
Generalized matching problems arise in a number of applications, including
computational advertising, recommender systems, and trade markets. Consider,
for example, the problem of recommending multimedia items (e.g., DVDs) to
users such that (1) users are recommended items that they are likely to be
interested in, (2) every user gets neither too few nor too many
recommendations, and (3) only items available in stock are recommended to
users. State-of-the-art matching algorithms fail at coping with large
real-world instances, which may involve millions of users and items. We
propose the first distributed algorithm for computing near-optimal solutions
to large-scale generalized matching problems like the one above. Our algorithm
is designed to run on a small cluster of commodity nodes (or in a MapReduce
environment), has strong approximation guarantees, and requires only a
poly-logarithmic number of passes over the input. In particular, we propose a
novel distributed algorithm to approximately solve mixed packing-covering
linear programs, which include but are not limited to generalized matching
problems. Experiments on real-world and synthetic data suggest that our
algorithm scales to very large problem sizes and can be orders of magnitude
faster than alternative approaches.
