Title | ||
---|---|---|
A new bound for the quadratic assignment problem based on convex quadratic programming |
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. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1007/PL00011402 | Math. Program. |
Keywords | Field | DocType |
Key words: quadratic assignment problem – eigenvalue bounds – quadratic programming – semidefinite programming,Mathematics Subject Classification (1991): 90C27,90C09,90C20 | Second-order cone programming,Discrete mathematics,Mathematical optimization,Quadratically constrained quadratic program,Quadratic assignment problem,Linear programming,Quadratic programming,Convex optimization,Semidefinite programming,Eigenvalues and eigenvectors,Mathematics | Journal |
Volume | Issue | ISSN |
89 | 3 | 0025-5610 |
Citations | PageRank | References |
29 | 4.81 | 20 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kurt M. Anstreicher | 1 | 633 | 86.40 |
Nathan Brixius | 2 | 122 | 15.20 |