# Technical Reports

## HPL-2012-40R1

**On Minimum-Cost Assignments in Unbalanced Bipartite Graphs**

* Ramshaw, Lyle; Tarjan, Robert E.*

HP Laboratories

HPL-2012-40R1

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

**Abstract:**
Consider a bipartite graph G = (X,Y;E) with real-valued weights on its edges, and suppose that G is *balanced*, with |X| = |Y|, The *assignment problem* asks for a perfect matching in G of minimum total weight. Assignment problems can be solved by linear programming, but fast algorithms have been developed that exploit their special structure. The famous Hungarian Method runs in time O(mn + n^2 log n), where n :=|X|=|Y| and m :=|E|. If the edge weights are integers bounded in absolute value by some constant C > 1, then algorithms based on *weight scaling*, such as that of Gabow and Tarjan, can lower the time bound to O(m sqrt(n) log(nC)).

But the graphs that arise in practice are frequently *unbalanced*, with r := min(|X|, |Y|) less than n := max(|X|, |Y|). Any matching in an unbalanced graph G has size at most r, and hence must leave at least n - r vertices in the larger part of G unmatched. We might want to find a matching in G of size r and of minimum weight, given that size. We can reduce this problem to finding a minimum-weight perfect matching in a balanced graph G' built from two copies of G. If we use such a doubling reduction when r << n, however, we get no benefit from r being small.

We consider problems of this type in graphs G that are unbalanced. More generally, given any s <= r, we consider finding a matching in G of size s and of minimum weight, given that size. The Hungarian Method extends easily to compute such a matching in time O(ms + s^2 log r). Note that all of the n's in the time bound for the balanced case have become either r's or s's, where s <= r <= n. But weight-scaling algorithms do not extend so easily. We introduce new machinery that enables us to compute a minimum-weight matching of size s in time O(m sqrt(s) log(sC)) via weight scaling. Our techniques give some insight into the general challenge of designing efficient, matching-related algorithms.

This report's key algorithm is presented more concisely in HPL-2012-72R1.

94 Pages

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

Internal Posting Date: October 19, 2012 [Fulltext]