This one has no reference in G&J, but I think it’s easy enough for me (or a student) to figure out.

**The problem: **Staff Scheduling. This is problem SS20 in the appendix.

**The description: **Given a collection C of m-tuples, each tuple consisting only of 0’s and 1’s, and each tuple having the same amount (k) of 1’s. These represent possible schedules we can give a worker. We’re also given a “requirement” m-tuple consisting of m non-negative integers, and a number N of workers. Can we map each c in C to a non-negative integer (representing the number of workers we assign to that schedule) such that the total number of all integers is N or less, and the requirement tuple is met?

**Example: **I think this is easier to explain with an example. Suppose we had 4-tuples (corresponding to 4 “work periods”) and C is the tuples:

0 | 0 | 1 | 1 |

1 | 1 | 0 | 0 |

1 | 0 | 0 | 1 |

0 | 1 | 1 | 0 |

0 | 1 | 0 | 1 |

Our requirement tuple is:

2 | 1 | 4 | 3 |

Then one possible schedule would be:

- 3 people with the first schedule (0,0,1,1)
- 2 people with the third schedule (1,0,0,1)
- 1 person with the fourth schedule (0,1,1,0)

..for a total of 6 workers. I think that’s the best you can do, since the first and third time periods have no schedules in common, and there is a total requirement of 6 workers for those time periods.

**Reduction:** G&J don’t give a reference, but they do suggest to use X3C. So we’re given a set X of 3q elements, and a collection C of 3-element subsets of X. The set C’ that we’ll build will be a set of “3q-tuples”, one position corresponding to each element in X. There will be one tuple for each triple in C. The tuples will have 1’s in the 3 positions corresponding to the elements in the triple in C, and 0’s everywhere else. The R-tuple will be all 1’s, and N will be equal to q.

The Staff Scheduling instance we’ve built needs to choose q different tuples to be successful, and that set of tuples will correspond to a solution to the original X3C instance.

**Difficulty: **4, assuming I didn’t miss anything. If you’ve previously explained X3C to your students, this would be a good homework problem.