A Weight-Scaling Algorithm for Min-Cost Imperfect Matchings in 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-72

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

美国|英语

来源: HP Labs

【 摘 要 】

Call a bipartite graph G=(X,Y;E) "balanced" when = 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 O(mn + n^2 log n), where n := = and m := 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( or, more generally, of some specified size s