An Assignment Problem Algorithm Using Minimum Cost Moving Method
Sang-Un Lee · Journal of the Korea Society of Computer and Information · 2015
Generally, the optimal solution of assignment problem has been obtained by Hungarian algorithm with O( $n^3$ ) time complexity. This paper proposes more simple algorithm with O( $n^2$ ) time complexity than Hungarian algorithm. The proposed algorithm simply selects minimum cost in each row, and classified into set S, H, and T. Then, the minimum cost is moved from S to T and $S{\rightarrow}H$ , $H{\rightarrow}T$ . The proposed algorithm can be obtain the same optimal solution as well-known algorithms and improve the optimal solution of partial unbalanced assignment problems.