Squared linear sum Is there any effective algorithm for a squared linear sum assignment problem?
For squared linear sum assignment problem I mean the following:
$$\min\left(\sum_i \sum_j c_{ij}x_{ij}\right)^2$$
with the conditions
$
\sum_j x_{ij}=1\\  
\sum_i x_{ij}=1\\  
x_{ij}\in\{0,1\}
$
 A: Here is an alternate formulation as a linear program.
Minimising $x^2$ is equivalent to minimising $|x|$. If you then define a new variable $u$ such that $x-u\leq My$ and $-u-x\leq M(1-y)$, $y=\{0,1\}$ and $M$ is some large number, you can solve the problem as $\min u$, with these extra constraints. These two constraints essentially ensure that $u\geq|x|$. You lose the structure of an assignment problem, but you do obtain a linear program.
Formulation:
$$\min u$$
$$Z\leq M(1-y)$$ $$ Z-u\leq My$$
$$-Z\leq My $$ $$ -u-Z\leq M(1-y)$$
$$\sum_i x_{ij}=1$$
$$\sum_j x_{ij}=1$$
$$y=\{0,1\}$$
$$x_{ij}=\{0,1\}$$
$$u\geq 0$$
where I have used $Z$ to represent your term inside the square in the objective function.
A: In other words, you want to find a permutation $\sigma$ that minimizes $|\sum_i c_{i\sigma(i)}|$?
That is NP-hard, by reduction from the subset sum problem, which asks, for a finite (multi)set of numbers $a_1,\ldots,a_n$, whether there is a nonempty subset that sums to 0.
Given an instance of subset sum, construct a $c_{ij}$ matrix of dimension $(2n-1)\times(2n-1)$ as follows:
$$C=\begin{bmatrix}
a_1 & a_1 & \cdots & a_1 & 0 & \cdots & 0 \\
a_2 & a_2 & \cdots & a_2 & 0 & \cdots & 0 \\
\vdots & \vdots &\ddots& \vdots & \vdots && \vdots \\
a_n & a_n & \cdots & a_n & 0 & \cdots & 0 \\
0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\
\vdots & \vdots && \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 0 & 0 & \cdots & 0
\end{bmatrix}$$
with $n$ copies of each $a_i$, $n-1$ columns of zeroes to the right, and $n-1$ rows of zeroes at the bottom.
Then $\min_\sigma |\sum_i c_{i\sigma(i)}|=0$ if and only if there's a nonempty subset of the $a_i$s that sums to $0$. (Clearly $\sum_i c_{i\sigma(i)}$ is always the sum of some subset of the $a_i$s, and it has to be a nonempty subset because there are not enough zero columns for the permutation to avoid all of them).
