The formal definition of the quadratic assignment problem is as follows: Usually weight and distance functions are viewed as square real-valued matrices, so that the cost function is written down as: In matrix notation: where
It was also proven that the problem does not have an approximation algorithm running in polynomial time for any (constant) factor, unless P = NP.
[2] The travelling salesman problem (TSP) 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 and all distances are equal to the respective distances of the TSP instance.
In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected electronic components onto a printed circuit board or on a microchip, which is part of the place and route stage of computer aided design in the electronics industry.
This type of QAP model was used in the design of the French keyboard standard (NF Z71-300).