A Universe of Sorts

§ Assignment Problem

Let $A$ be an $n \times n$ non-negative matrix.
A permutation $\sigma$ of $[1, \dots, n]$ is called a simple assignment if $A[i][\sigma(i)]$ is positive for all $i$ .
A permutation $\sigma$ is called as an optimal assignment if $\sum_i A[i][\sigma(i)]$ is minimized over all permutations in $S_n$ . (weird? Don't we usually take max?)
Matrix $A[p][j]$ is the cost of assigining person $p$ the job $j$ . Want to minimize cost.

[10 12 19 11]
[5  10 07 08]
[12 14 13 11]
[8  15 11  9]

First find some numbers $u[i]$ and $v[i]$ (these correspond to dual variables in the LP) such that $a[i][j] \leq u[i] + v[j]$ for all $i, j$

     v[1] v[2] v[3] v[4]
u[1] [10  12  19   11]
u[2] [5   10  07   08]
u[3] [12  14  13   11]
u[4] [8   15  11    9]

We can start by setting $u[r] = 0$ , $v[c] = \min[r](a[r][c])$ . (Can also take $v[c] = 0$ but this is inefficient)
Circle those positions where equality holds. This becomes:

     v[1] v[2] v[3] v[4]
u[1] [10  12   19    11]
u[2] [5#  10#  07#   08#]
u[3] [12  14   13    11]
u[4] [8   15   11     9]

Since $a[i][j] \leq u[i] + v[j]$ , this implies that $a[i][\sigma(i)] \geq u[i] + v[\sigma(i)]$ .
This means $\sum a[i][\sigma(i)] \geq \sum_i u[i] + v[\sigma(i)] = \sum_i u[i] + v[i]$ (the summation can be rearranged).
Now think of the bipartite graph where these circled positions correspond to $1$ , the rest correspond to $0$ s. If we have a perfect matching amongst the circled positions, then that is the solution (??)
If the circled positions DO NOT have a perfect matching, then by Fobenius Konig, we can write the matrix as:

    s  n-s
n-r[B | C]
r  [X | D]

r + s = n + 1

where in $X$ , no entry is circled, because entries that are circled correspond to zeroes (conceptually?)
We add $1$ to $u[\geq (n-r)]$ s D. We subtract $1$ for $v[\geq s]$ . That is:

    -1
   B C
+1 X D

Nothing happens to $B$ .
in $C$ , $v$ goes down, so that keeps the inequality correct.
In $X$ , there are no circles, which means everything was a strict ineuality, so we can afford to add 1s.
In $D$ , $u$ goes up by $1$ , $v$ goes down by $1$ , thus total no change? [I don't follow ].
The net change is going to be $+1(r) - 1 (n - s) = r + s - n = (n+1) - n = 1$ .
The nonconstructive part is decomposing the matrix into $[B; C, X, D]$ .