## § 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.

#### § 4x4 example

• Let the cost be:
[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]$.

#### § Hungarian algorithm

• Take minimum in each row, subtract.
• Take minimumin each col, subtract.