# 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},`

`}`