On Minimum-Cost Assignments in Unbalanced Bipartite Graphs

Ramshaw, Lyle ; Tarjan, Robert E.

HP Development Company

关键词: assignment problem;    imperfect matching;    minimum-cost matching;    unbalanced bipartite graph;    weight-scaling algorithm;   

RP-ID  :  HPL-2012-40

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Consider a bipartite graph G = (X,Y;E) with real- valued weights on its edges, and suppose that G is "balanced", with = 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 := = and m := 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( less than n := max( . 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