| Article ID: | iaor19911378 |
| Country: | Germany |
| Volume: | 21 |
| Start Page Number: | 189 |
| End Page Number: | 195 |
| Publication Date: | May 1990 |
| Journal: | Optimization |
| Authors: | Bookhold I. . |
The paper discusses special cases of the quadratic assignment problem (QAP) being polynomially solvable. In particular it gives an algebraic condition for the cost matrices of a QAP which guarantees that it is equivalent with a linear assignment problem. Based on these results the paper develops an approximation algorithm for QAI’s with non-negative symmetric cost matrices.