MPI-INF/SWS Research Reports 1991-2021

1. Author,Editor - 3. with BibTeX cite keys


A distributed algorithm for large-scale generalized matching

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

April 2013, 39 pages.

Status: available - back from printing

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.

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},