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?
