Talk:Quadratic assignment problem

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)

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)