An O(n4) Algorithm for the QAP Linearization Problem

• 成果类型: Article
• 署名作者: Kabadi, Santosh N.; Punnen, Abraham P.
• 署名单位: University of New Brunswick; Simon Fraser University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0509
• 发表日期: 2011
• 页码: 754-761
• 关键词: assignment; VALUES

摘要

An instance of the quadratic assignment problem (QAP) with cost matrix Q is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix C such that for each assignment, the QAP and LAP objective function values are identical. Several sufficiency conditions are known that guarantee linearizability of a QAP. However, no polynomial time algorithm is known to test if a given instance of QAP is linearizable. In this paper, we give a necessary and sufficient condition for an instance of a QAP to be linearizable and develop an O(n(4)) algorithm to solve the corresponding linearization problem, where n is the size of the QAP.