In the "Setting" section of the Wikipedia page for the Hungarian algorithm, it says:

"We are given a nonnegative $n×n$ matrix, where the element in the i-th row and j-th column represents the cost of assigning the j-th job to the i-th worker. We have to find an assignment of the jobs to the workers that has minimum cost."

Why does the cost matrix have to be nonnegative?

  • $\begingroup$ I bet in some step of the algorithm you have to take a minimum with respect to some of those values/sums of those values and if the numbers were negative, you could keep on adding a specific cost that the solution would always be getting better. $\endgroup$ – RGS Nov 30 '16 at 0:44
  • $\begingroup$ if you get a problem with some negative entries, you add a constant to all the entries. This does not change the optimal assignment, $\endgroup$ – Will Jagy Nov 30 '16 at 1:06
  • $\begingroup$ @WillJagy Thanks, I understand that. However, I would like to know why it is required (if it really is) for the cost matrix to be nonnegative rather than how to modify a matrix to make it satisfy the requirement. $\endgroup$ – user3731622 Dec 1 '16 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.