3
$\begingroup$

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?

$\endgroup$
3
  • $\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
    Commented Nov 30, 2016 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
    Commented Nov 30, 2016 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
    Commented Dec 1, 2016 at 1:12

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .