Journal article
Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem
SIAM journal on optimization, Vol.11(1), pp.254-265
2000
DOI: 10.1137/S1052623499354904
Abstract
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 "projected eigenvalue bound" is one of the best available bounds for the QAP, especially when considering the quality of bounds relative to the complexity of obtaining them. In this paper we show that the projected eigenvalue bound is also related to an SDP relaxation of the original QAP. This "implicit" SDP relaxation is similar to SDP relaxations of the QAP proposed by Lin and Saigal [On Solving Large-scale Semidefinite Programming Problems---A Case Study of Quadratic Assignment Problem, Department of Industrial Engineering and Operations Research, University of Michigan, 1997] and Zhao et al. [J. Combin. Optim., 2 (1998), pp. 71-109].
Details
- Title: Subtitle
- Eigenvalue Bounds Versus Semidefinite Relaxations for the Quadratic Assignment Problem
- Creators
- K. M Anstreicher
- Resource Type
- Journal article
- Publication Details
- SIAM journal on optimization, Vol.11(1), pp.254-265
- Publisher
- Society for Industrial and Applied Mathematics
- DOI
- 10.1137/S1052623499354904
- ISSN
- 1052-6234
- eISSN
- 1095-7189
- Language
- English
- Date published
- 2000
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380404302771
Metrics
1 Record Views