MPII20051001
Rankmaximal through maximum weight matchings
Michail, Dimitrios
February 2005, 22 pages.
.
Status: available  back from printing
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 rankmaximal 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 rankmaximal 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 rankmaximal 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} (ri)}$.
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 maximumweight matching
problem can help us derive an efficient algorithm.

 Attachement: MPII20051001.ps (447 KBytes)
URL to this document: https://domino.mpiinf.mpg.de/internet/reports.nsf/NumberView/20051001
BibTeX
@TECHREPORT{Michail2005,
AUTHOR = {Michail, Dimitrios},
TITLE = {Rankmaximal through maximum weight matchings},
TYPE = {Research Report},
INSTITUTION = {MaxPlanckInstitut f{\"u}r Informatik},
ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPII20051001},
MONTH = {February},
YEAR = {2005},
ISSN = {0946011X},
}