Quadratic assignment problem: Difference between revisions

Revision as of 22:29, 4 June 2012

Revision as of 14:56, 1 December 2012

Line 22:

:<math>\sum_{a,b\in P}w_{a,b}d_{f(a),f(b)}</math>

== [[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 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.

Line 40:

[[Category:NP-hard problems]]

[[Category:combinatorialCombinatorial optimization]]

[[es:Problema de la asignación cuadrática]]