On Minimum-Cost Assignments in Unbalanced Bipartite Graphs
Ramshaw, Lyle; Tarjan, Robert E.
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.
External Posting Date: October 19, 2012 [Fulltext]. Approved for External Publication
Internal Posting Date: October 19, 2012 [Fulltext]