Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

A more general form of the quadratic assignment problem includes a linear term as well. See Pardalos, Rendl, and Wolkowicz, "The Quadratic Assignment Problem: A Survey and Recent Developments," DIMACS Series in Discrete Mathematics and Theoretical Computer Science.

The explanation of why this is quadratic seem wrong... says the cost function is in terms of "quadratic inequalities", but I don't see inequalities anywhere in the problem statement. It might be helpful to cite some of the other representations of the problem instead, including

$\min _{x}\sum _{i,j,k,l}a_{ij}b_{kl}x_{ik}x_{jl}+\sum _{i,j}c_{ij}x_{ij}$

and

${\mbox{Trace}}[(AXB+C)X^{T}]$

where x is a binary permutation matrix and A, B, and C are square nxn matrices. Thse are also from the Pardalos paper.

Danbob00 (talk) 20:09, 17 March 2008 (UTC)[reply]

Complexity

What is the least known upper bound on the complexity? It would be nice to have that in the article. 72.75.124.183 (talk) 20:33, 13 September 2008 (UTC)[reply]