AN EFFICIENT COST SCALING ALGORITHM FOR THE INDEPENDENT ASSIGNMENT PROBLEM
Satoru Fujishige, Zhang Xiaodong · Journal of the Operations Research Society of Japan · 1995
An efficient cost scaling algorithm is presented for the independent assignment problem of Iri and Tomizawa, which is equivalent to the weighted matroid intersection problem of Edmonds. Our algorithm in general can be viewed as a generalization of Orlin and Ahuja's scaling algorithm for the ordinary assignment problem. On a bipartite graph with n vertices and integer arc costs bounded by C, an optimal r-independent assignment can be found in O(√