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

```
[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.