Quadratic assignment problem: Difference between revisions

Revision as of 22:01, 14 July 2005

Revision as of 01:32, 10 September 2005

Line 22:

== [[Computational complexity]] ==

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 facilities only along a single ring, all flows havinghave the valuesame of(constant) 1value. Many other problems of standard [[combinatorial optimization]] problems may be written in this form.

== Applications ==