Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem

It was recently demonstrated that a well-known eigenvalue bound for the qua dratic assignment problem (QAP) actually corresponds to a semidefinite prog ramming ( SDP) relaxation. However, for this bound to be computationally us eful, the assignment constraints of the QAP must rst be eliminated and the bound then applied to a lower-dimensional problem. The resulting projected eigenvalue bound is one of the best available bounds for the QAP, especiall y when considering the quality of bounds relative to the complexity of obta ining them. In this paper we show that the projected eigenvalue bound is al so related to an SDP relaxation of the original QAP. This implicit SDP rela xation is similar to SDP relaxations of the QAP proposed by Lin and Saigal [On Solving Large-scale Semidefinite Programming Problems A Case Study of Q uadratic Assignment Problem, Department of Industrial Engineering and Opera tions Research, University of Michigan, 1997] and Zhao et al. [J. Combin. O ptim., 2 (1998), pp. 71-109].