[Rule] 3-PARTITION to DYNAMIC STORAGE ALLOCATION

[isPANN]

Source: 3-PARTITION
Target: DYNAMIC STORAGE ALLOCATION
Motivation: Establishes NP-completeness (in the strong sense) of Dynamic Storage Allocation by reduction from 3-Partition. The reduction encodes the partition constraint as a memory packing constraint: each integer a_i becomes a storage item of that size, and all items coexist in the same time interval. The memory bound D = mB forces the items to pack perfectly, and the size constraint B/4 < a_i < B/2 guarantees exactly 3 items per group of sum B. This is the original proof referenced in Garey & Johnson (SR2), attributed to Stockmeyer (1976, private communication).

Reference: Garey & Johnson, Computers and Intractability, SR2, p.226

GJ Source Entry

[SR2] DYNAMIC STORAGE ALLOCATION
INSTANCE: Set A of items to be stored, each a∈A having a size s(a)∈Z^+, an arrival time r(a)∈Z_0^+, and a departure time d(a)∈Z^+, and a positive integer storage size D.
QUESTION: Is there a feasible allocation of storage for A, i.e., a function σ: A→{1,2,...,D} such that for every a∈A the allocated storage interval I(a)=[σ(a),σ(a)+s(a)-1] is contained in [1,D] and such that, for all a,a'∈A, if I(a)∩I(a') is nonempty then either d(a)<=r(a') or d(a')<=r(a)?
Reference: [Stockmeyer, 1976b]. Transformation from 3-PARTITION.
Comment: NP-complete in the strong sense, even if s(a)∈{1,2} for all a∈A. Solvable in polynomial time if all item sizes are the same, by interval graph coloring algorithms (e.g., see [Gavril, 1972]).

Reduction Algorithm

Given a 3-Partition instance: a set S = {a_1, a_2, ..., a_{3m}} of 3m positive integers with Σ a_i = mB and B/4 < a_i < B/2 for all i (so every valid partition has exactly 3 elements per group).

Construct the following Dynamic Storage Allocation instance:

1. Items: For each integer a_i ∈ S, create a storage item with:

   • Size: s(a_i) = a_i
   • Arrival time: r(a_i) = 0
   • Departure time: d(a_i) = 1

   All 3m items are present during the single time interval [0, 1), so every pair of items has overlapping time intervals.

2. Memory size: Set D = mB.

Correctness:

• Since all items share the time interval [0, 1), their memory intervals must be pairwise non-overlapping.
• The total size of all items is Σ a_i = mB = D, so the items must pack the memory [1, D] exactly with no gaps.
• Any feasible packing partitions the items into contiguous groups along the memory axis. Because B/4 < a_i < B/2, no two items can sum to B or more, and no four items can sum to B or less. Therefore each contiguous group of items filling a block of size B must contain exactly 3 items summing to B.
• (==>) A valid 3-Partition {S_1, ..., S_m} with each |S_j| = 3, Σ_{a∈S_j} a = B directly yields a packing: place the items of S_1 in positions [1, B], items of S_2 in [B+1, 2B], etc.
• (<==) A feasible allocation packs all items into [1, mB] with no overlap and no gaps. The items in positions [1, B] must sum to exactly B (since each item has size > B/4, at most 3 fit; since each has size < B/2, at least 3 are needed). Repeating for each block [jB+1, (j+1)B] gives the 3-Partition.

Size Overhead

Symbols:

• n = 3m = number of integers in the 3-Partition instance (num_integers of source)
• B = target sum per group (target_sum of source)

Target metric (code name)	Polynomial (using symbols above)
num_items	num_integers
memory_size	num_integers * target_sum / 3

Derivation: Each of the 3m integers becomes one item. Memory size D = mB = (3m/3) * B = num_integers * target_sum / 3.

Validation Method

Closed-loop test: Construct a small 3-Partition instance with a known valid partition. Apply the reduction to obtain a DynamicStorageAllocation instance. Solve the DSA instance (by brute force). Verify that:

1. A feasible storage allocation exists if and only if a valid 3-Partition exists.
2. The allocation can be decoded back: items packed into contiguous blocks of size B identify the partition groups.
3. On a NO-instance (modify one a_i so no partition summing to B exists), no feasible allocation exists.

Example

3-Partition instance:

• S = {5, 6, 7, 5, 7, 6} (3m = 6, m = 2, B = 18)
  • Check: B/4 = 4.5, B/2 = 9, all a_i ∈ (4.5, 9) ✓
  • Σ a_i = 36 = 2 * 18 = mB ✓

Valid partition: {5, 6, 7} and {5, 7, 6}, each sums to 18.

DSA instance:

• 6 items, all with arrival time 0, departure time 1:

Item	Size	Arrival	Departure
i1	5	0	1
i2	6	0	1
i3	7	0	1
i4	5	0	1
i5	7	0	1
i6	6	0	1

• Memory size D = 36

Feasible allocation: σ(i1)=1, σ(i2)=6, σ(i3)=12, σ(i4)=19, σ(i5)=24, σ(i6)=31.

• i1 occupies [1, 5], i2 occupies [6, 11], i3 occupies [12, 18] -- group 1: 5+6+7 = 18 = B ✓
• i4 occupies [19, 23], i5 occupies [24, 30], i6 occupies [31, 36] -- group 2: 5+7+6 = 18 = B ✓
• All intervals non-overlapping, all within [1, 36] ✓

The grouping {i1, i2, i3} and {i4, i5, i6} corresponds to the 3-Partition {5, 6, 7} and {5, 7, 6}.

References

• [Stockmeyer, 1976b]: [Stockmeyer1976b] Larry J. Stockmeyer (1976). "private communication".
• [Gavril, 1972]: [Gavril1972] F. Gavril (1972). "Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph". SIAM Journal on Computing 1, pp. 180-187.