본문 바로가기
  • Home

The Grid Type Quadratic Assignment Problem Algorithm

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2014, 19(4), pp.91-99
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

TThis paper suggests an heuristic polynomial time algorithm to solve the optimal solution forQAP (quadratic assignment problem). While Hungarian algorithm is most commonly used for alinear assignment, there is no polynomial time algorithm for the QAP. The proposed algorithmderives a grid type layout among unit distances of a distance matrix. And, we apply max-flow/min-distance approach to assign this grid type layout in such a descending order way that thelargest flow is matched to the smallest unit distance from flow matrix. Evidences from implementationresults of the proposed algorithm on various numerical grid type QAP examples show that asolution to the QAP could be obtained by a polynomial algorithm.

Citation status

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