Search by:
Year of publication
Author name
Paper title
Recurrent method for solving the assignment problem
Full text (PDF)
UDC: 519.161
Publication Language: Russian
Stuc. intelekt. 2014; 19(2):107–118
Abstract: The article proposes new method for solving the assignment problem based on recursive obtaining an optimal solution. It consists in finding a minimum weighted matchings total weight in a bipartite graph, using concepts the shortest increasing path. The proposed method allows to obtain solutions of the assignment problem is significantly faster than existing methods.
Keywords: the assignment problem, matching, bipartite graph, increasing path
References:
- Papadimitriou C. Combinatorial Optimization: Algorithms and Complexity / C. Papadimitriou, K. Steiglitz. –M.: Mir, 1985. – 510 p.
- Panishev А.V. Fast algorithm for solving the assignment problem for finding lower bounds on the cost of theroute of a Salesman / A.Y. Levchenko, A.V. Morozov, A.V. Panishev // Artificial intelligence The Institute ofArtificial Intelligence.– Donetsk, 2011 .– P. 406-416.
- Levchenko A.Y. Acceleration mechanism in the Little’s method for solving problems in the class of aSalesman / A.Y. Levchenko, A.V. Morozov, A.V. Morozov // Artificial intelligence The Institute of ArtificialIntelligence.– Donetsk, 2012. – P. 95-110.