Title: A new method of solving the assignment problem based on the permissible-edge algorithm of minimum cost flow problem
Abstract: A new algorithm of the assignment problem is proposed by constructing its minimum cost maximum flow model and applying the permissible-edge algorithm based on the principle of duality to the model.The new algorithm gradually expands the permissible network in the capacity-cost network by means of modifying the potential of labeled nodes subject to complementary slackness condition,and then augments flows on the permissible network,which proceeds until the minimum cost maximum flow of the original capacity-cost network is obtained.The non-zero edge of this maximum flow corresponds to the optimal solution of the assignment problem.During the iterating process,successive iteration will fully use the information of previous ones,which effectively reduces the computation.For non-standard assignment problems,this algorithm can be directly applied without converting the problem to the standard form.
Publication Year: 2012
Publication Date: 2012-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot