hide
Free keywords:
-
Abstract:
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.
