Minimizing the maximum cost of job assignment problem

Question

I need to develop a polynomial-time algorithm for this problem but I'm a little confused. I need to minimize the maximum cost among the assignments, not the total cost of all assignments. I tried using the Hungarian method but it finds the minimum total cost, not minimum of the maximum value.

How should I go about it?

Answer 1

Sort the weights, do binary search for the minimum maximum, check each guess by subsetting the edges not greater than the candidate maximum and running Hopcroft–Karp.