Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


A distributed algorithm for large-scale generalized matching

Makari, Faraz and Gemulla, Rainer and Khandekar, Rohit and Mestre, Julian and Sozio, Mauro

MPI-I-2013-5-002. April 2013, 39 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-2013-5-002.pdfMPI-I-2013-5-002.pdf547 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Makari, Faraz and Gemulla, Rainer and Khandekar, Rohit and Mestre, Julian and Sozio, Mauro},
  TITLE = {A distributed algorithm for large-scale generalized matching},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2013-5-002},
  MONTH = {April},
  YEAR = {2013},
  ISSN = {0946-011X},