最小化作业分配问题的最大成本 [英] Minimizing the maximum cost of job assignment problem

问题描述

我需要为这个问题开发一个多项式时间算法，但我有点困惑.我需要最小化作业中的最大成本，而不是所有作业的总成本.我尝试使用匈牙利方法，但它找到了最小的总成本，而不是最大值的最小值.

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.

我应该怎么做?

推荐答案

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

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.

这篇关于最小化作业分配问题的最大成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！