# D2: Allocation

Today is Sports Day at World of Math!

Your task is to pick a dream team of students to do a relay race. Each student must be assigned one part of the race to run.
The legs are: *Egg & Spoon*, *Backwards Running*, *Hopping* and *Skipping*. Each athlete has promised
that they will achieve their personal best in whatever part of the race you ask them to do. The personal bests are given in
this table.

Egg & Spoon | Backwards Running | Hopping | Skipping | |
---|---|---|---|---|

Amos | 20 | 22 | 14 | 24 |

Biff | 20 | 19 | 12 | 20 |

Cecil | 13 | 10 | 18 | 16 |

Dave | 22 | 23 | 9 | 28 |

Now try to pick a team of World Beaters.

## Cost Reduction

The Hungarian algorithm is quite difficult to understand; I'll try my best to explain *why* it works.

First, we try to simplify the numbers in the table. Notice that Amos will take *at least 14* seconds, regardless
of what event he does. We could subtract 14 from all of his personal best times. I have called this the *basic time*
and now the time for the Egg & Spoon for Amos is his basic time (14) plus the extra (6).

Egg & Spoon | Backwards Running | Hopping | Skipping | Basic Time | |
---|---|---|---|---|---|

Amos | 6 | 8 | 0 | 10 | 14 |

Biff | 20 | 19 | 12 | 20 | |

Cecil | 13 | 10 | 18 | 16 | |

Dave | 22 | 23 | 9 | 28 |

I now repaeat this for the other contestants. This process is called *row reduction*.

Egg & Spoon | Backwards Running | Hopping | Skipping | Basic Time | |
---|---|---|---|---|---|

Amos | 6 | 8 | 0 | 10 | 14 |

Biff | 8 | 7 | 0 | 8 | 12 |

Cecil | 3 | 0 | 8 | 6 | 10 |

Dave | 13 | 14 | 0 | 19 | 9 |

Now look at the *columns*. Regardless of who runs the Egg & Spoon race, the time will be at least 3 seconds more
than the basic time for the athlete. Amos takes 8 seconds more than his basic time, etc. The basic add-on time for Egg &
Spoon is 3 seconds, so we could deduct this from all the times, knowing that whoever runs the Egg & Spoon will add at least 3 seconds
to the basic times.

Egg & Spoon | Backwards Running | Hopping | Skipping | Basic Time | |
---|---|---|---|---|---|

Amos | 3 | 8 | 0 | 10 | 14 |

Biff | 5 | 7 | 0 | 8 | 12 |

Cecil | 0 | 0 | 8 | 6 | 10 |

Dave | 10 | 14 | 0 | 19 | 9 |

Basic add-on | 3 |

From the above table we see that Dave takes 10 seconds *more* than his basic time (9) plus the Egg& Spoon add-on (3).
This is not a good event for Dave. I repeat this *column reduction* for the remaining events.

Egg & Spoon | Backwards Running | Hopping | Skipping | Basic Time | |
---|---|---|---|---|---|

Amos | 3 | 8 | 0 | 4 | 14 |

Biff | 5 | 7 | 0 | 2 | 12 |

Cecil | 0 | 0 | 8 | 0 | 10 |

Dave | 10 | 14 | 0 | 13 | 9 |

Basic add-on | 3 | 0 | 0 | 8 |

I'm getting a bit fed up with all these tables, so I'll explain in a clip instead.

## The Hungarian Algorithm

## Variations

The Hungarian algorithm is a *minimising* algorithm and there are three special cases of which we need to be aware.

### Maximising Problems

If we are running a business and need to *maximise* an allocation problem, we change the values to represent
how much *change* we'd give, and try to *minimise* that total. Eg Four people I, II, III and IV are going to buy
stuff of us. The amount they'll each pay is in the table.

A | B | C | D | |
---|---|---|---|---|

I | 20 | 22 | 14 | 24 |

II | 20 | 19 | 12 | 20 |

III | 13 | 10 | 18 | 16 |

IV | 22 | 23 | 9 | 28 |

Pretend that they all pay £30. The *change* we give them is therefore:

A | B | C | D | |
---|---|---|---|---|

I | 10 | 8 | 16 | 6 |

II | 10 | 11 | 18 | 10 |

III | 17 | 20 | 12 | 14 |

IV | 8 | 7 | 21 | 2 |

We now try to minimise the change we give (this is equivalent to maximising the costs).

Note that I subtracted from £30. In reality I would subtract from £28 as this is the highest number in the original table.

### Gaps In The Table

If Amos was unwilling to do the skipping race, we could get round that by making up a ridiculously high number for his time,
and proceed as usual. *How high is ridiculously high?* In a 4x4 table the maximum that the answer can be is 4×
the highest number, since we use four numbers in total. To ensure we don't accidentally make Amos do the skipping race, we make
his time greater than 4× the biggest number.

Egg & Spoon | Backwards Running | Hopping | Skipping | |
---|---|---|---|---|

Amos | 20 | 22 | 14 | - |

Biff | 20 | 19 | 12 | 20 |

Cecil | 13 | 10 | 18 | 16 |

Dave | 22 | 23 | 9 | 28 |

becomes

Egg & Spoon | Backwards Running | Hopping | Skipping | |
---|---|---|---|---|

Amos | 20 | 22 | 14 | 100 |

Biff | 20 | 19 | 12 | 20 |

Cecil | 13 | 10 | 18 | 16 |

Dave | 22 | 23 | 9 | 28 |

The 100 is more than 4× the highest number, so Amos can relax - we won't be using him for the skipping race.

### More Rows Than Columns Or Vice Versa

If there wasn't a skipping race, then one athlete would have no event to run. In the case of having an oblong matrix
(eg 3 by 4), we add a *dummy* row/column with zeros in it, much like we did in the
transportation section.

Egg & Spoon | Backwards Running | Hopping | |
---|---|---|---|

Amos | 20 | 22 | 14 |

Biff | 20 | 19 | 12 |

Cecil | 13 | 10 | 18 |

Dave | 22 | 23 | 9 |

becomes

Egg & Spoon | Backwards Running | Hopping | Dummy | |
---|---|---|---|---|

Amos | 20 | 22 | 14 | 0 |

Biff | 20 | 19 | 12 | 0 |

Cecil | 13 | 10 | 18 | 0 |

Dave | 22 | 23 | 9 | 0 |

and we proceed as before.