Minimize Maximum Cost

Question

Given N jobs and M tasks, assign K jobs to K tasks where K<=(min(M,N)), so that the max_cost out of K jobs is minimized.

Can you help me with algorithm for the problem. I have tried brute force but I dosen't work for large inputs. Can we use DP here?

Answer 1

I solved similar problem using Hopcroft-Karp Problem. First of all find cost between all tasks and jobs. Now loop through all the costs and see if there is a bipartite graph with cardinality K. If it is there than that cost is the answer. If not move to next cost, and add the additional edge to graph and check again, until you reach a graph where cardinality can be K.

Answer 2

You can solve the problem "is there a solution with max cost X" by testing if there's a matching of size K in the bipartite graph where nodes are jobs and tasks, and there's an edge between a job and a task if the cost of the job doing that task is at most X. You can use the Hopcroft-Karp algorithm for this, which is polynomial time.

Then you can use a binary search to find the smallest X where the sub-problem is still feasible.

Answer 3

A possible approach would be to find the max cost by bisection.

For a given max cost x, it is possible to perform the assignment if and only if it is possible to match K jobs to K tasks in a reduced graph where all edges with cost>x have been removed.

You can test whether this assignment is possible by measuring the size of the maximum bipartite matching using, for example the Hopcroft-Karp algorithm.