After CSC’16 (cont’): The best paper

Now that the Proceedings of the CSC Workshop 2016 has appeared (link), we can look at the papers. In this post, we are going to look at the best paper by Manne, Naim, Lerring, and Halappanavar, “On stable marriages and greedy matchings” (doi).

As noted in the citation of the award, this paper brings together  recent half-approximation algorithms  for  weighted matchings  and the classical  Gale-Shapley and McVitie-Wilson algorithms for the Stable Marriage problem. This is helpful in two ways.

First, the authors show that a  recent half-approximation algorithm for computing greedy matchings, the Suitor algorithm and its variants,  is equivalent to  the classical algorithms for the Stable Marriage problem. This correspondence enables the authors to propose multi-core and many-core parallel algorithms for the Stable Marriage problem, based on the greedy matching algorithms. This way, if I am not mistaken, they develop the first GPU algorithm for the Stable Marriage problem.

Second, the extensive theoretical work on the Stable Marriage algorithms  explains the  behavior of the Suitor matching algorithm. The worst-case number of proposals in the Suitor algorithm can be O(n^2),  where n is the number of vertices  in the bipartite graph. However, if the weights are assigned randomly, the expected number of proposals is O(n \log n), which follows from a classical analysis of Donald Knuth [1, 2].

This work represents a nice marriage between theory and practice: the practical algorithms for the greedy matching help in designing parallel algorithms for the Stable Marriage problem, and the theoretical understanding of the Stable Marriage problem sheds light into the behavior of the greedy weighted matching algorithms.

Vocabulary

Stable marriage problem: This is described on a full bipartite graph G=(L\cup R, L\times R).  Each vertex on the left has a total ranking of the vertices on the right; similarly each vertex on the right has a total ranking of all vertices on the left. The aim is to find a matching M such that no l\in L and r\in R  would obtain a higher ranked partner if they were to abandon their current partners in M and rematch with each other.

Greedy matching algorithm: Here we compute approximations to matchings of maximum  weight in weighted graphs. The Greedy algorithm  considers edges in a non-increasing order of weights and the heaviest remaining edge (u,v) is added to the matching, whereupon all edges incident on u and v are removed. The Greedy matching is a half-approximate matching.

Suitor algorithm: This is a proposal based algorithm [3]. Vertices can propose in any order, however, each vertex proposes to a neighbor with the  heaviest weight  that already does not have a better weight offer to match with it.  A vertex could annul the proposal received by a neighbor if it has a better weight edge to offer the neighbor.  When two vertices propose to each other, they are matched. The Suitor algorithm computes the same matching as the one obtained by the Greedy algorithm and the Locally Dominant edge algorithm described by Robert Preis [4]!

References

  1. Vicki Knoblauch, Marriage matching: A conjecture of Donald Knuth, Economics Working Papers. Paper 200715, http://digitalcommons.uconn.edu/econ_wpapers/200715, 2007.
  2. Donald E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, Vol. 10 American Mathematical Society, (1997).
  3. Fredrik Manne and Mahantesh Halappanavar, New effective multithreaded matching algorithms, in Proc. IPDPS 2014, IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, pp. 519–528, 2014.
  4. Robert Preis, Linear time 1/2-approximation algorithm for maximum weighted matching in general graphs, in Proc. STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science Trier, Germany, pp. 259–269, 1999.
Advertisements