An efficient cost scaling algorithm for the independent assignment problem

An efficient cost scaling algorithm for the independent assignment problem

0.00 Avg rating0 Votes
Article ID: iaor19961783
Country: Japan
Volume: 38
Issue: 1
Start Page Number: 124
End Page Number: 136
Publication Date: Mar 1995
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: programming: integer, programming: assignment
Abstract:

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. The present 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 equ1 time by our algorithm under an independence oracle for matroids.

Reviews

Required fields are marked *. Your email address will not be published.