본문 바로가기
  • Home

An Assignment Problem Algorithm Using Minimum Cost Moving Method

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(8), pp.105-112
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

Generally, the optimal solution of assignment problem has been obtained by Hungarian algorithm with O(n3) time complexity. This paper proposes more simple algorithm with O(n2) 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→H, H→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.

Citation status

* References for papers published after 2022 are currently being built.