The Hungarian algorithm Flashcards
Studying this course? Keep your progress in one place.

Flip each card. Be honest: the ones you mark Not yet come back first.
12 cards
Tap a card to flip it. Swipe right if you knew it, left if not.
See all 12 cards
- What does the Hungarian algorithm find?
- A complete one-to-one allocation of workers to tasks with the least total cost.
- In which order are matrix reductions done?
- Rows first (subtract each row minimum), then columns.
- How do you test whether an allocation is ready?
- Cover all zeros with the fewest straight lines; ready if the number of lines equals .
- What do you do if fewer than lines are needed?
- Subtract the smallest uncovered entry from uncovered entries, add it to entries covered twice, then re-test.
- What happens to entries covered by exactly one line when augmenting?
- They are unchanged.
- From which matrix is the final cost found?
- The original cost matrix, not the reduced one.
- What is a dummy location?
- An extra row or column of equal entries (normally ) that makes the matrix square when numbers are unequal.
- What does being matched with the dummy mean?
- The worker or task does not take part in the allocation, and adds no cost.
- How do you handle a pairing that is impossible?
- Put a very large number in that cell.
- How is a maximum profit problem converted?
- Subtract every entry from the largest entry in the original matrix, then minimise.
- After converting, how is the maximum profit found?
- From the original profit matrix, using the allocation found.
- Why does subtracting a constant from a row not change the best allocation?
- Every complete allocation uses exactly one entry from that row, so all totals fall by the same amount.