The following problem is from a past algorithms course exam and I'm using it to test my knowledge.

There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a capacity $C_i$, meaning that it has $C_i$ units of processing time. Each job $j$ has a demand $D_j$, meaning that it requires $D_j$ units of processing time to complete. We'd like to assign all the jobs to the machines, so that each job is assigned to only one machine, and no machine is overloaded (i.e. the total demands assigned to machine i doesn't exceed its capacity $C_i$).

Input: $m$ positive numbers $C_1,\cdots, C_m$, n positive numbers $D_1,\cdots, D_n$, and for each $1\leq i\leq m$ and $1\leq j\leq n,$ a boolean variable $x_{i,j}$ indicating whether machine $i$ can do job $j$.

Output: Does there exist an assignment such that all the jobs are assigned to machines, so that each job is assigned to only one machine and no machine is overloaded?

Question: prove the above problem is NP-complete, or give an algorithm to solve the decision problem in polynomial time.

I think the problem might be NP-complete. The decision problem asks whether an assignment assigns at least k jobs, where k is a parameter to the decision problem. Clearly the problem is in NP; one can verify in polynomial time that an assignment satisfies that no machine is overloaded and each job is assigned to one machine. One can do this by checking the jobs assigned to machine i and verifying that the total sum of the $D_j$'s associated with machine i is at most $C_i$. One can then check at the same time that no job is assigned to two different machines.

But I'm not sure which NP-complete problem to reduce from. For instance, I know the following well-known problems are NP-complete: vertex cover, 3-SAT, hamiltonian cycle, set cover, hamiltonian path, clique, independent set, 3 coloring, subset sum etc.

Maybe Vertex cover would be useful?


1 Answer 1


This problem is a generalization of the decision version of the bin packing problem (BPP). While all bins in BPP have the same given capacity, the capacities of the machines in this problem are variable.

The decision version of BPP is $\mathsf{NP}$-complete. So you have guessed correctly: this problem is $\mathsf{NP}$-complete since this problem is in $\mathsf{NP}$ as proved in the question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.