Hello Codeforces community,
I have come across this problem and I would like some help.
You are given N machines and M jobs. Each machine has a processing power P_i (integer). Each job requests a processing power P_j (integer). A job j is complete when it has a total of P_j power coming from 1 or more machines. A machine can provide some part of it's power to one or more jobs.
It's guaranteed that sum of machine power = sum of job request power. Which means all jobs can be completed.
I want to minimize the number of assignments (machine, job).
Example:
Machine A (50)
Machine B (30)
Machine C (40)
Job A (70)
Job B (50)
Minimum assignments: 3
(machine A sends 50 to job B)
(machine B sends 30 to job A)
(machine C sends 40 to job A)
Is there any algorithm that solves this? (excluding brute force)
It sounds like the Generalized assignment problem, but with less restrictions. https://en.wikipedia.org/wiki/Generalized_assignment_problem
This is a bipartide graph, with integer flows and balanced.
The closest solution I got is (aside from brute force) to try a mincost-maxflow algorithm setting the imbalances and enforcing a fixed cost (say 1) to use one edge (independent of the amount of flow). However I am not sure if that works, because there is also the dual problem using potential and reduced costs. I don't know how to handle that on this problem.
Thanks!