Can I use the Hungarian algorithm to determine the maximum cost?

Question

The Hungarian algorithm solves the problem of assignment in polynomial time. Given the work and tasks and the n × n matrix containing the costs of assigning each employee to a task, he can find a task to minimize costs.

I want to find a choice for which the maximum cost? Can I do this using the Hungarian or any similar method? Or can this be done only exponentially?

Answer 1

As David said in a comment:

Multiply the cost matrix by -1 for maximization. 

Answer 2

Wikipedia says:

If the goal is to find the destination that gives the maximum value, the problem can be changed to fit the setting, replacing each value with a maximum value deducted from the value.

So, if I understand correctly: among all the costs that you have as input, you will find the maximum value. Then you replace each value x with max - x . That way, you still have positive costs, and you can run the Hungarian algorithm.

They say otherwise: Hungarian is trying to minimize the cost of the appointment. So, if you are looking for the maximum, you can change the cost: x → -x. However, some implementations (I don’t know if they are all or all) require positive numbers. Therefore, the idea is to add a constant value to each value in order to have positive numbers. This constant value does not change the resulting affectation.