Quadratic Assignment Problem via a Convex and Concave Relaxations Procedure
Lei He, Zhiyong Liu, Min Liu, Xu Yang, Fengyi Zhang · 2018
The convex and concave relaxations procedure (CCRP) was recently proposed to approximately solve the graph matching problem and exhibited a quite promising performance. To extend the CCRP to approximately solve the quadratic assignment problem (QAP), a major trouble is how to figure out the corresponding convex and concave relaxation functions. In this paper we will propose a general but simple QAP algorithm, and will then prove that the algorithm is exactly an type of CCRP algorithm, but without needing to figure out the convex or concave relaxation function in an explicit way. The proposed algorithm can be generally used on symmetric and asymmetric QAP's, and is simple to implement. Extensive experimental comparisons on the QAPLib benchmark data sets witness a state-of-the-art performance of the proposed algorithm.