International Federation of Automatic Control |
Session WA3: Computational Algorithms for Control DesignChair: Michel Gevers - Belgium Co-chair: Karolos Grigoriadis - United States Room: Santiago 2007-10-17 From 13:30 to 15:30 | |
Reduceness Properties and Applications to the Optimal Assignment Problem E. Sagianos; N. Karcanias Contact: Evangelos Sagianos - United Kingdom | |
14:30-14:50 | |
Abstract: | |
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. Copyright © 2007 IFAC. |