Efficient Go Bags

Consider a set of n items I. You have purchased k copies of each item as well as k bags. Each bag can hold all or any subset of the n items of I. The goal is to preload the k bags so that if you need a certain subset S of the items I, then there is a bag B that contains a superset of S. The efficiency of B for S is |S|/|B|, that is the number of items in S divided by the number in B. We denote this eff(B,S)

The worst-case efficiency of the set of bags is the minimum over all sets S of the efficiency of the most efficient bag for S. That is min_S (max_B (eff(B,S)).

Warm-Up: Suppose there are 10 items and there are three bags. Which items would you put into each bag to get the highest possible worst-case efficiency?

Solution to Warm-Up: {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Any single item will be covered by one of the first two bags yielding an efficiency of 1/5. Any pair will be covered by the bag with all the items, giving a worst-case efficiency of 2/10. Any larger group would also be covered by the bag with all items and will have a higher efficiency. Thus, the worst-case efficiency is 1/5.

Question: Are 11 bags enough to get a worst-case efficiency of 1/4?

Solution: We will still need a bag with all items. The other bags should contain four or fewer items so that they can cover any singleton with efficiency of 1/4. Those other bags must also cover all pairs. If not, then the all-item bag must be used for at least some pairs giving a worst-case efficiency of only 1/5.

In addition to the bag with all items {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, here is a set of 10 bags that cover all pairs: {1, 2, 3, 4}, {1, 5, 6, 7}, {8, 1, 10, 9}, {2, 3, 5, 6}, {8, 2, 3, 7}, {3, 9, 2, 10}, {8, 4, 5, 6}, {9, 4, 5, 7}, {9, 10, 4, 6}, {10, 5, 7}. End of solution.

So far, we have limited the solutions to take just one bag, but suppose one could take two bags B1 and B2. In that case, the efficiency for a set of needed items S would be |S|/(|B1| + |B2|).

To see that this could help, consider the following problem.

Question: Assume a set of 10 items as before, but one is allowed to take two bags. Can one achieve an efficiency of 1/3 with six bags?

Solution: Let the bags be {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 1, 4}. Any singleton gets an efficiency of 1/3 by choosing the appropriate single bag with three items in them. Any pair can be handled by two of the three-item bags. Regarding triplets, the argument is a little more subtle. At least two items in the triplet must belong to one of the five-item bags (if not, then each five-item bag would hold only one item or fewer and that would not make up a triplet). If all three belong to one of the five-item bags, then the efficiency is 3/5. Otherwise, take the five-item bag holding two items and any three-item bag holding the remaining item. This gives an efficiency of 3/8. If S is of size four or greater, then the two five-item bags will give an efficiency of 4/10 or greater.

Upstart: Given a worst-case efficiency goal and the ability to take b bags when there are n items, how many bags are required?