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


Rank-maximal through maximum weight matchings

Michail, Dimitrios

MPI-I-2005-1-001. February 2005, 22 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
Given a bipartite graph $G( V, E)$, $ V = A \disjointcup B$
where $|V|=n, |E|=m$ and a partition of the edge set into
$r \le m$ disjoint subsets $E = E_1 \disjointcup E_2
\disjointcup \dots \disjointcup E_r$, which are called ranks,
the {\em rank-maximal matching} problem is to find a matching $M$
of $G$ such that $|M \cap E_1|$ is maximized and given that
$|M \cap E_2|$, and so on. Such a problem arises as an optimization
criteria over a possible assignment of a set of applicants to a
set of posts. The matching represents the assignment and the
ranks on the edges correspond to a ranking on the posts submitted
by the applicants.

The rank-maximal matching problem has been previously
studied where a $O( r \sqrt n m )$ time and linear
space algorithm~\cite{IKMMP} was
presented. In this paper we present a new simpler algorithm which
matches the running time and space complexity of the above
The new algorithm is based on a different approach,
by exploiting that the rank-maximal matching problem can
be reduced to a maximum weight matching problem where the
weight of an edge of rank $i$ is $2^{ \ceil{\log n} (r-i)}$.
By exploiting that these edge weights are steeply distributed
we design a scaling algorithm which scales by a factor of
$n$ in each phase. We also show that in each phase one
maximum cardinality computation is sufficient to get a new
optimal solution.

This algorithm answers an open question raised on the same
paper on whether the reduction to the maximum-weight matching
problem can help us derive an efficient algorithm.
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-2005-1-001.ps447 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 = {Michail, Dimitrios},
  TITLE = {Rank-maximal through maximum weight matchings},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2005-1-001},
  MONTH = {February},
  YEAR = {2005},
  ISSN = {0946-011X},