Quadratic assignment problem: Difference between revisions

Revision as of 21:06, 26 June 2005

Revision as of 03:04, 27 June 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 simplified[[Travelling salesman problem]] may be seen as a special case whenof allQAP, if one assumes that the flows areconnect equalfacilities toonly 1along isa alsosingle NP-hardring, all flows having the value of 1. Many other problems of standard [[combinatorial optimization]] problems may be written in this form.

== Applications ==