An O(n
4) Algorithm for the QAP Linearization Problem

An O(n 4) Algorithm for the QAP Linearization Problem

0.00 Avg rating0 Votes
Article ID: iaor201111572
Volume: 36
Issue: 4
Start Page Number: 754
End Page Number: 761
Publication Date: Nov 2011
Journal: Mathematics of Operations Research
Authors: ,
Keywords: quadratic assignment
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.