# Technical Reports

## HPL-2012-72R1

**A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in Bipartite Graphs**

* Ramshaw, Lyle; Tarjan, Robert E.*

HP Laboratories

HPL-2012-72R1

**Keyword(s):** assignment problem; imperfect matching; minimum-cost- matching; unbalanced bipartite graph; weight-scaling algorithm

**Abstract:**
Call a bipartite graph G=(X,Y;E) *balanced* when |X|=|Y| Given a balanced bipartite graph G with edge costs, the *assignment problem* asks for a perfect matching in G of minimum total cost. The Hungarian Method can solve assignment problems in time space O(m) and time O(mn + n^2 log n), where n :=|X|=|Y| and m :=|E|. If the edge weights are integers bounded in magnitude by C > 1, then algorithms using *weight scaling*, such as that of Gabow and Tarjan, can lower the time to O(m sqrt(n) log(nC)).

There are important applications in which G is *unbalanced*, with not equal to and we require a min-cost matching in G of size r := min(|X|, |Y|) or, more generally, of some specified size s <= r. The Hungarian Method extends easily to find such a matching in time O(ms + s^2 log r), but weight-scaling algorithms do not extend so easily. We introduce new machinery that allows us to find such a matching in time O(m sqrt(s) log(sC)) via weight scaling. Our results provide some insight into the design space of efficient weight-scaling matching algorithms.

These ideas are presented in greater depth in HPL-2012-40R1.

25 Pages

External Posting Date: October 19, 2012 [Fulltext]. Approved for External Publication

Internal Posting Date: October 19, 2012 [Fulltext]