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:
Our requirement tuple is:
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.