4
$\begingroup$

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\} $

2 Answers 2

2

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.

  • 0
    Yes, it makes sense now :-)2012-09-21
1

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).