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