Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Why isn't the solution to this program $u=0$? If $Z$ takes at least one positive value $Z_+$, then $y=1$, $Z=Z_+$ and $u=0$ is a solution, and if $Z$ takes at least one negative value $Z_-$, then $y=0$, $Z=Z_-$ and $u=0$ is a solution. Or am I missing something? –  joriki Sep 21 '12 at 10:50
    
@joriki I had a sign wrong in my working. I have fixed it now. –  Daryl Sep 21 '12 at 11:12
    
If $Z$ takes negative values, $u=0$ is still a solution (now with either $y=0$ or $y=1$). –  joriki Sep 21 '12 at 11:15
    
I was right the first time. Let me think for a moment to describe it. I may also have royally screwed up... –  Daryl Sep 21 '12 at 11:27
    
I think that is good now @joriki. There was a few negative signs going astray. –  Daryl Sep 21 '12 at 12:02
show 1 more comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.