edufgf's blog

By edufgf, history, 8 years ago, In English

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!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by edufgf (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Assume there are only two jobs, and they require the same processing power.

Then assigning machines to these two jobs is an instance of the partition problem, which is NP-complete.

Since this very simple subcase is already NP-complete, I have some doubts that you'll be able to find something much quicker than brute force for the general problem.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh Thanks! I guess I will just go for some non-optimal greedy approach.