 max planck institut
informatik MPI-I-2005-1-001

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
algorithm.
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.
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s): 447 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: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2005-1-001 BibTeX
@TECHREPORT{Michail2005,
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},
}