1

http://tom.host.cs.st-andrews.ac.uk/CS3052-CC/Practicals/Kuhn.pdf

Is the paper. I am looking at the definition of transfer, essential, inessential and the proof of theorem 1.

Consider qualification matrix Q i=1,2 j=1,2 with every entry is 1. Then consider the assignment 1->1 , 2->2

I believe if I understand the papers definitions, there is only the null transfer (no change) possible for this assignment and it is complete after every transfer. Then also, both individuals are inessential and both jobs are essential. Is this correct? Or does munkres allow j0=jr in his transfer definition despite referring to j0 as unassigned?

Then looking at theorem 1, "if i is assigned to another job then j is unassigned and Lemma 2 asserts that the individual i is essential". Consider i=1,j=2. We know from Q, i is qualified for j. We know i is assigned to another job j'=1 but it doesn't seem to follow that j is unassigned (job 2 is assigned to individual 2) so Lemma 2 didn't hold here.

How can I resolve this? I think I must misunderstand a definition somewhere.

topoquestion
  • 867

2 Answers2

0

I've looked at this some more and an convinced the proof is faulty but the conclusion is right.

The second case in the proof can be extended as follows:

If j is unassigned, L2 shows i is essential (as the paper says ), but by the above counter example, j can be assigned.

If j is assigned, and there isn't a transfer that leaves j unassigned, then by L3, j is essential.

If j is assigned, and there exists a transfer that leaves j unassigned, then there must exist a transfer that includes i to j from j2 so i is essential.

The rest of the proof is correct.

topoquestion
  • 867
0

The proof is not wrong. In your example the individuals are essential, but the jobs are not. For any assignment, jobs are essential if and only if they are assigned to some inessential individual.

Robert Badea
  • 396