Since Bin Packing was a redo, here is the first real problem in the Storage and Retrieval section.
The problem: Dynamic Storage Allocation. This is problem SR2 in the appendix.
The description: Given a set A of items. Each item a in A has size s(a), arrival time r(a) and departure time d(a) (all positive integers). We’re also given a storage size D. Can we allocate the items to D “slots” of storage such that:
- Each item is stored in consecutive slots. So an element a has to be contained in s(a) adjacent locations from 1 to D.
- No two items overlap the same slot during the time they are in storage. In other words, if two items a and a’ are mapped to the same slot in D, the must not have any overlap between their arrival and departure times.
Example: Here’s a simple set of items:
If D=6, we can store these items by using slots 1-4 to hold both items 1 and 2 (notice that they don’t overlap in time, and having one item arrive right as the other departs is ok), and slots 5-6 to hold item 3.
Reduction: The reference to Stockmeyer in G&J is to a private communication. I tried working out my own reduction from 3-Partition, but couldn’t make it work. My approach was to make the sizes of the elements in the 3-Parttion instance map to times in this problem, since G&J give the hint that you can make all sizes 1 or 2. But I couldn’t figure out how to make it work. I sort of expect there to be 3 possible sizes for a 3-partition problem, instead of 2.
Eventually, I found a paper by Lim that uses regular Partition, using the storage allocation problem as a special case of a problem involving berthing ships. (The ship problem adds extra complications like each ship needing a specified clearance between it and other ships). He starts with a set A of elements, and defines T to be the sum of all of the element sizes. He then creates one item in the storage allocation problem for each element in S. For a given s(a) in A, the new item has size s(a), arrival time 2, departure time 3 (so exist for just one time duration) . He also adds 9 new items that have the effect of creating only two sequences of storage slots that can hold the items from s, each of size= T/2. We can place the items in these slots if and only if there is a partition of S.
Difficulty: 7. I don’t think the idea is too hard to understand, but the 9 sets that are created are hard to come up with (even if you can understand what their purpose is, coming up with the sets that actually get that purpose accomplished is pretty hard).