A new bound for the quadratic assignment problem based on convex quadratic programming |
| |
| Authors: | Kurt M Anstreicher Nathan W Brixius |
| |
| Institution: | (1) Department of Management Sciences, University of Iowa, Iowa City, IA 52242, e-mail: kurt-anstreicher@uiowa.edu, US;(2) Department of Computer Science, University of Iowa, Iowa City, IA 52242, e-mail: brixius@cs.uiowa.edu, US |
| |
| Abstract: | We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound
uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known
projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and
computational effort.
Received: February 2000 / Accepted: November 2000?Published online January 17, 2001 |
| |
| Keywords: | : quadratic assignment problem – eigenvalue bounds – quadratic programming – semidefinite programming |
| 本文献已被 SpringerLink 等数据库收录！ |
|
