Quadratic assignment problem: Difference between revisions

Revision as of 04:48, 20 May 2010

Revision as of 14:10, 25 October 2010

Line 23:

The problem is [[NP-hard]], so there is no known [[algorithm]] for solving this problem in polynomial time, and even small instances may require long computation time. The [[Travelling salesman problem]] may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value. Many other problems of standard [[combinatorial optimization]] problems may be written in this form.

A considerable amount of research in [[ant colony optimization]], a biologically-inspired heuristic, has centered on solving the QAP by achieving as good an approximation as possible.

== Applications ==