REDUCENESS PROPERTIES AND APPLICATIONS TO THE OPTIMAL ASSIGNMENT PROBLEM

The paper deals with a new approach to the solution of the optimal assignment problem, which can be formulated in terms of integer matrices, and is thus connected to graph theory and matroids. Such problems arise in structural system identification, resource allocation, transportation problems, etc. Current approaches rely on exhausting searches, graph theory and linear programming techniques. The new approach is based in the notion of extended reduceness of Boolean matrices, which exploits the structure of the specific problem and reduces the computational effort and the complexity. The connection of the new structural approach to bipartite graphs, matroids and linear programming is established.