algorithm - 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

对权重进行排序，对最小最大值进行二分搜索，通过对不大于候选最大值的边进行子集化并运行 Hopcroft-Karp 来检查每个猜测。