MINIMUM QUADRATIC 0-1 ASSIGNMENT

• INSTANCE: Nonnegative integer $n\times n$-matrix $C\in N^{n\cdot n}$, nonnegative integer $m\times m$-matrix $D\in N^{m\cdot m}$.

• SOLUTION: Binary $n\times m$-matrix $X\in \{0,1\}^{n\cdot m}$ such that there is at most one 1 in each row of X and exactly one 1 in each column of X.

• MEASURE: $$\sum\limits_{i,j=1\atop i\not=j}^{n} \displaystyle\sum\limits_{k,l=1\atop k\not=l}^{m} C_{i,j} D_{k,l} X_{i,k} X_{j,l}$$.

  
  

• Bad News: Not in APX [426].

• Comment: Not in APX even if D satisfies the triangle inequality [411].