[Model] DynamicStorageAllocation

[isPANN]

Motivation

DYNAMIC STORAGE ALLOCATION (P150) from Garey & Johnson, A4 SR2. A classical NP-complete problem modeling the packing of variable-sized items into a fixed-size memory, where each item has a known arrival time and departure time. Items occupying overlapping time intervals must not overlap in memory space. This is equivalent to a strip packing problem with fixed item widths and time-constrained placement.

Associated rules:

• [Rule] 3-PARTITION to DYNAMIC STORAGE ALLOCATION #828/[Rule] 3-PARTITION to DYNAMIC STORAGE ALLOCATION #397: 3-PARTITION → DynamicStorageAllocation (NP-completeness in the strong sense, Stockmeyer 1976)

The problem is NP-complete in the strong sense, even when item sizes are restricted to {1, 2}. It becomes polynomial when all item sizes are equal (reducible to interval graph coloring).

Definition

Name: DynamicStorageAllocation

Reference: Garey & Johnson, Computers and Intractability, A4 SR2

Mathematical definition:

INSTANCE: Set A of items to be stored, each a ∈ A having a size s(a) ∈ Z+, an arrival time r(a) ∈ Z0+, 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)?

Variables

• Count: |A| (one variable per item, representing its starting address in memory)
• Per-variable domain: {1, 2, ..., D - s(a) + 1} — the starting address for item a, constrained so the item fits within [1, D]
• Meaning: σ(a) ∈ {1, ..., D - s(a) + 1} assigns each item a starting memory address. The item occupies addresses [σ(a), σ(a) + s(a) - 1]. Two items whose time intervals overlap (neither departs before the other arrives) must have non-overlapping memory intervals.

Schema (data type)

Type name: DynamicStorageAllocation
Variants: none (general item set with time intervals and sizes)

Field	Type	Description
items	Vec<(usize, usize, usize)>	Items: (arrival_time, departure_time, size) for each a ∈ A
memory_size	usize	Storage size D

Notes:

• This is a feasibility (decision) problem: Value = Or.
• Key getter methods: num_items() (= |A|), memory_size() (= D).

Complexity

• Decision complexity: NP-complete in the strong sense (Stockmeyer, 1976; transformation from 3-Partition). NP-complete even with item sizes restricted to {1, 2}. Polynomial when all item sizes are equal (interval graph coloring, Gavril 1972).
• Best known exact algorithm: Brute-force enumeration of starting addresses gives O(D^|A|) in the worst case. No pseudo-polynomial algorithm exists unless P = NP (strong NP-completeness).
• Concrete complexity expression: "(memory_size + 1)^num_items" (for declare_variants!)
• Approximation: Factor 3 approximation by Gergov (1999). Improved to (2+ε) by Mömke & Wiese (2015).
• References:
  • L.J. Stockmeyer (1976). Cited in Garey & Johnson as the source of the NP-completeness proof.
  • J. Gergov (1999). "Algorithms for Compile-Time Memory Optimization." SODA 1999, pp. 907-908.
  • F. Gavril (1972). "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph." SIAM J. Comput. 1(2), pp. 180-187.

Extra Remark

Full book text:

INSTANCE: Set A of items to be stored, each a ∈ A having a size s(a) ∈ Z+, an arrival time r(a) ∈ Z0+, 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]).

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all possible starting addresses σ(a) for each item; verify no two time-overlapping items have overlapping memory intervals.)
• It can be solved by reducing to integer programming. (ILP with integer variables σ_a for starting address of each item; constraints: 1 ≤ σ_a ≤ D - s(a) + 1; for each pair (a, a') with overlapping time intervals, add non-overlap constraints on memory intervals using big-M or indicator variables. Companion rule issue to be filed separately.)
• Other: First-Fit Decreasing and other heuristics for practical instances.

Example Instance

Input:
A = {a_1, a_2, a_3, a_4, a_5} (5 items), memory size D = 6.

Item	Arrival r(a)	Departure d(a)	Size s(a)
a_1	0	3	2
a_2	0	2	3
a_3	1	4	1
a_4	2	5	3
a_5	3	5	2

Peak load analysis (maximum total size at any time):

• Time [1,2): a_1 + a_2 + a_3 = 2+3+1 = 6 = D (tight)
• Time [2,3): a_1 + a_3 + a_4 = 2+1+3 = 6 = D (tight)
• Time [3,4): a_3 + a_4 + a_5 = 1+3+2 = 6 = D (tight)

Solution: σ(a_1)=1, σ(a_2)=3, σ(a_3)=6, σ(a_4)=3, σ(a_5)=1.

• a_1 occupies [1,2] during [0,3)
• a_2 occupies [3,5] during [0,2)
• a_3 occupies [6,6] during [1,4)
• a_4 occupies [3,5] during [2,5) — a_2 departs at time 2, a_4 arrives at time 2, no time overlap ✓
• a_5 occupies [1,2] during [3,5) — a_1 departs at time 3, a_5 arrives at time 3, no time overlap ✓

All 7 time-overlapping pairs verified: no memory conflicts. All items fit within [1,6]. ✓
Answer: YES — a feasible storage allocation exists.

Non-trivial structure: The memory is completely full at three distinct time intervals (peak load = D = 6). Items a_4 and a_5 must reuse memory addresses freed by a_2 and a_1 respectively — a greedy left-to-right allocation would fail.

Negative modification: Increase s(a_3) from 1 to 2. Now peak load at time [1,2) is 2+3+2=7 > 6, so no allocation can fit all items. Answer: NO.

Python validation script

items = [(0,3,2), (0,2,3), (1,4,1), (2,5,3), (3,5,2)]  # (arrival, departure, size)
D = 6
sigma = [1, 3, 6, 3, 1]  # starting addresses

# Check all items fit within [1, D]
for i, (r, d, s) in enumerate(items):
    assert 1 <= sigma[i] and sigma[i] + s - 1 <= D

# Check no time-overlapping pairs have memory overlap
for i in range(5):
    for j in range(i+1, 5):
        ri, di, si = items[i]; rj, dj, sj = items[j]
        time_overlap = not (di <= rj or dj <= ri)
        if time_overlap:
            li, hi = sigma[i], sigma[i]+si-1
            lj, hj = sigma[j], sigma[j]+sj-1
            mem_overlap = not (hi < lj or hj < li)
            assert not mem_overlap, f"Items {i},{j} conflict"

print("All verified: feasible allocation")

# Negative: increase s(a3) to 2, peak load exceeds D
items_neg = [(0,3,2), (0,2,3), (1,4,2), (2,5,3), (3,5,2)]
# At time [1,2): items 0,1,2 present, sizes 2+3+2=7 > 6
peak = max(sum(s for r,d,s in items_neg if r <= t < d) for t in range(5))
assert peak > D
print(f"Negative: peak load {peak} > {D} (infeasible)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not in reduction graph; planned reduction from 3-Partition
Non-trivial	✅ Pass	Distinct feasibility constraints (time-interval-aware memory packing) unlike any existing problem
Correctness	⚠️ Warn	Approximation claim mixes up attribution; complexity expression missing
Well-written	❌ Fail	Missing concrete complexity expression; no companion ILP rule issue linked; example has residual confusion

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

The problem DynamicStorageAllocation does not exist in the current reduction graph (pred show DynamicStorageAllocation fails). It is listed as G&J A4 SR2, a well-known NP-complete problem in the Storage and Retrieval category. The issue mentions a planned reduction R88: 3-PARTITION → DynamicStorageAllocation, which would connect it to the existing graph. Brute-force and ILP solver paths are identified. Pass.

Non-trivial

This problem is genuinely distinct from existing problems. While there are storage-related problems in the codebase (RootedTreeStorageAssignment, BinPacking), DynamicStorageAllocation has a fundamentally different structure: items have temporal intervals (arrival/departure times) and spatial sizes, and the feasibility constraint requires non-overlap in the memory dimension only for items whose time intervals overlap. This is not a variant of BinPacking (no bins, single memory strip with temporal dimension) or RootedTreeStorageAssignment (tree structure, no temporal aspect). Pass.

Correctness

3a — Definition: The formal definition is well-formed and matches the standard G&J formulation. The feasibility constraint (non-overlapping memory intervals for temporally overlapping items) is correctly stated. ✅

3b — Complexity:

• The issue correctly states NP-complete in the strong sense (consistent with G&J SR2).
• The reference "[Stockmeyer, 1976b]" is consistent with G&J bibliography conventions.
• The claim "NP-complete even if s(a) ∈ {1,2}" is consistent with G&J's comment on SR2. ✅
• The claim "solvable in polynomial time if all item sizes are the same, by interval graph coloring" citing [Gavril, 1972] is consistent — Gavril 1972 gave polynomial algorithms for chordal/interval graph problems. ✅

3c — Approximation claim issue: The issue states "best known polynomial-time approximation achieves a factor of 3 [Buchsbaum et al., 2004; Gergov, 1999]." This is partially incorrect:

• Gergov (1999) achieved a 3-approximation — correct.
• Buchsbaum, Karloff, Kenyon, Reingold, Thorup (2004) in "OPT versus LOAD in Dynamic Storage Allocation" (SIAM J. Comput. 33(3):632–646) did NOT achieve a factor-3 approximation. Their result relates OPT to LOAD (the maximum demand at any time point). The attribution is misleading.
• ⚠️ Warn — not a fatal error since the factor-3 bound from Gergov is correct, but the Buchsbaum et al. citation is misattributed.

Recommendation: A (2+ε)-approximation algorithm for DSA was later achieved by Mömke & Wiese (2015, ESA; journal version in Algorithmica 2017). Consider updating the approximation discussion.

3d — Missing concrete complexity expression: The Complexity section describes NP-completeness and approximation results but does not provide a concrete worst-case complexity expression for an exact algorithm (e.g., D^num_items or (D * T)^num_items). This is needed for declare_variants!. ⚠️ Warn.

Well-written

4a — Information Completeness:

• ✅ Motivation: Present with concrete use case (memory packing)
• ✅ Name: DynamicStorageAllocation — no optimization prefix needed for a feasibility problem
• ✅ Reference: G&J SR2 cited
• ✅ Definition: Complete formal definition with input, feasibility constraint
• ✅ Variables: Count, domain, meaning all specified
• ✅ Schema: Type name and field table present
• ❌ Complexity: Missing concrete complexity expression. The section discusses NP-completeness and approximation but does not provide a formula like D^num_items that would go into declare_variants!. This is required per template.
• ❌ How to solve: ILP is checked but no companion [Rule] DynamicStorageAllocation to ILP issue is linked. Per template requirements, a direct ILP path claim must link a companion rule issue.
• ✅ Example Instance: Present with worked solution
• ✅ Expected Outcome: YES answer with verified allocation

4b — Definition Completeness: The definition is precise and implementable. All quantifiers are explicit. ✅

4c — Symbol and Notation Consistency: Symbols (A, s(a), r(a), d(a), D, σ, I(a)) are consistently used across Definition, Variables, and Example sections. ✅

4d — Example Quality:

• The example has 5 items and D=6, providing a reasonably non-trivial instance. ✅
• The example shows the self-correction process (initial solution had a conflict, revised solution is correct). The final solution is verified with all time-overlapping pairs checked. ✅
• However, the example would benefit from removing the erroneous first attempt (the "Revised solution" label and error trail are confusing for paper presentation). ⚠️ Minor.
• The example only demonstrates a YES instance. A NO instance or at least a note about when it becomes infeasible would strengthen the example. ⚠️ Minor.

Overall Well-written verdict: ❌ Fail due to missing complexity expression and missing ILP companion rule issue link.

Recommendations

• Add a concrete complexity expression for the best-known exact algorithm (e.g., "(memory_size + 1)^num_items" for brute-force enumeration of starting addresses, or research if a better exact algorithm exists).
• Create and link a companion [Rule] DynamicStorageAllocation to ILP issue, or remove the ILP checkbox.
• Fix the approximation attribution: Gergov (1999) achieved factor 3; Buchsbaum et al. (2004) proved a different result (OPT vs LOAD relationship). Consider citing Mömke & Wiese (2015/2017) for the improved (2+ε)-approximation.
• Clean up the example to remove the erroneous first attempt and present only the correct solution.

[isPANN]

Fix-issue changelog

• Example: Removed failed first solution attempt (a1/a4 memory conflict at [1,3]). Kept only the correct revised solution with peak-load analysis.
• Complexity: Fixed approximation attribution — Gergov (1999) = factor 3, not Buchsbaum et al. Added Mömke & Wiese (2+ε). Added concrete expression "(memory_size + 1)^num_items" for declare_variants!.
• Associated rules: Linked rule issues [Rule] 3-PARTITION to DYNAMIC STORAGE ALLOCATION #828/[Rule] 3-PARTITION to DYNAMIC STORAGE ALLOCATION #397 (3-PARTITION → DynamicStorageAllocation).
• ILP: Added companion rule note.
• Schema notes: Added getter methods (num_items(), memory_size()).
• Added negative example (increase s(a3) to 2, peak load 7 > D=6) and Python validation script.

Applied by /fix-issue.

[isPANN]

Please kindly check the following items (PR #960):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.