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.**↵
↵
The bold parts above are what makes it different than the standard assignment problem.↵
↵
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!↵
↵
↵
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.**↵
↵
The bold parts above are what makes it different than the standard assignment problem.↵
↵
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!↵
