Hungarian algorithm: Difference between revisions

Revision as of 11:30, 18 July 2024

Revision as of 21:31, 20 July 2024

Line 525:

If the number of starred zeros is {{mvar|n}} (or in the general case <math>min(n,m)</math>, where {{mvar|n}} is the number of people and {{mvar|m}} is the number of jobs), the algorithm terminates. See the [[#Result|Result]] subsection below on how to interpret the results.

'''Otherwise, find the lowest uncovered value. Subtract this from every unmarked element and add it to every element covered by two lines. Go back to step 4.'''

This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments.