Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment pro blem

Kurt Anstreicher

It was recently demonstrated that a well-known eigenvalue bound for the Quadratic Assignment Problem (QAP) actually corresponds to a semidefinite programming (SDP) relaxation. However, for this bound to be computationally useful the assignment constraints of the QAP must first be eliminated, and the bound then applied to a lower-dimensional problem. The resulting

Dept. of Management Sciences, University of Iowa, February 1999

Contact: kurt-anstreicher@uiowa.edu