[Model] ExpectedRetrievalCost

[isPANN]

Motivation

EXPECTED RETRIEVAL COST (P152) from Garey & Johnson, A4 SR4. An NP-complete problem (in the strong sense) from the Storage and Retrieval category. It models the optimization of record placement on drum-like storage devices (rotating storage media with fixed-position read heads), where the goal is to distribute records across m sectors to minimize the expected rotational latency. The problem captures the trade-off between access probability and physical sector distance on a circular layout. NP-complete even for fixed m >= 2 (though solvable in pseudo-polynomial time per fixed m). The main reduction is from PARTITION / 3-PARTITION.

Associated rules:

• R098: Partition / 3-Partition → Expected Retrieval Cost (as target)

Definition

Name: ExpectedRetrievalCost
Canonical name: EXPECTED RETRIEVAL COST
Reference: Garey & Johnson, Computers and Intractability, A4 SR4, p.227

Mathematical definition:

INSTANCE: Set R of records, rational probability p(r) in [0,1] for each r in R, with sum_{r in R} p(r) = 1, number m of sectors, and a positive integer K.
QUESTION: Is there a partition of R into disjoint subsets R_1, R_2, ..., R_m such that, if p(R_i) = sum_{r in R_i} p(r) and the "latency cost" d(i,j) is defined to be j - i - 1 if 1 <= i < j <= m and to be m - i + j - 1 if 1 <= j <= i <= m, then the sum over all ordered pairs i,j, 1 <= i,j <= m, of p(R_i) * p(R_j) * d(i,j) is at most K?

Variables

• Count: n = |R| variables. Each variable x_r in {1, 2, ..., m} assigns record r to a sector.
• Per-variable domain: {1, 2, ..., m} — the sector index to which each record is assigned.
• dims(): vec![m; n] — each of the n records can be assigned to one of m sectors.
• Meaning: The variable assignment encodes a partition of records into m sectors. Record r is placed in sector x_r. The objective is to find an assignment such that the weighted latency cost sum_{i,j} p(R_i)*p(R_j)*d(i,j) <= K, where the latency d(i,j) measures the circular distance from sector i to sector j on the drum.

Schema (data type)

Type name: ExpectedRetrievalCost
Variants: none (no type parameters)

Field	Type	Description
probabilities	Vec<f64>	Access probability p(r) for each record r in R; must sum to 1.0
num_sectors	usize	Number of sectors m on the drum-like device
bound	f64	Maximum allowable expected retrieval cost K

Size field getters:

• num_records() → probabilities.len() (n = |R|)
• num_sectors() → num_sectors (m)

Notes:

• This is a satisfaction (decision) problem: Metric = bool, implementing SatisfactionProblem.
• The latency function d(i,j) is implicit and computed from the circular sector layout: d(i,j) = (j - i - 1) mod m for the "forward" direction, specifically d(i,j) = j - i - 1 if i < j, and d(i,j) = m - i + j - 1 if j <= i. Note d(i,i) = m - 1 (full rotation when head is already at sector i and next request is also sector i).
• The probabilities are rational numbers in [0,1], but for implementation purposes we use f64.
• The original GJ formulation uses "positive integer K", but the cost function computes products of rational probabilities × integer latencies, yielding rational (not necessarily integer) values. We use f64 for both probabilities and the bound to avoid the complexity of exact rational arithmetic, which is standard practice for this type of problem.

Complexity

• Best known exact algorithm: For fixed m, the problem is solvable in pseudo-polynomial time via dynamic programming. For general m, it is strongly NP-complete. Brute-force: enumerate all m^n assignments of records to sectors, compute cost for each; time O(m^n * m^2). No sub-exponential exact algorithm is known for general m.
• Concrete complexity string: "num_sectors ^ num_records" (brute-force enumeration of all sector assignments)
• NP-completeness: NP-complete in the strong sense [Cody and Coffman, 1976], via reduction from 3-PARTITION.
• Approximation: Cody and Coffman showed that highest-access-frequency-first assignment heuristics provide near-optimal solutions with provable worst-case bounds.
• References:
  • R. A. Cody and E. G. Coffman, Jr. (1976). "Record allocation for minimizing expected retrieval costs on drum-like storage devices." Journal of the ACM 23(1):103-115.

Extra Remark

Full book text:

INSTANCE: Set R of records, rational probability p(r) in [0,1] for each r in R, with sum_{r in R} p(r) = 1, number m of sectors, and a positive integer K.
QUESTION: Is there a partition of R into disjoint subsets R_1, R_2, ..., R_m such that, if p(R_i) = sum_{r in R_i} p(r) and the "latency cost" d(i,j) is defined to be j - i - 1 if 1 <= i < j <= m and to be m - i + j - 1 if 1 <= j <= i <= m, then the sum over all ordered pairs i,j, 1 <= i,j <= m, of p(R_i) * p(R_j) * d(i,j) is at most K?
Reference: [Cody and Coffman, 1976]. Transformation from PARTITION, 3-PARTITION.
Comment: NP-complete in the strong sense. NP-complete and solvable in pseudo-polynomial time for each fixed m >= 2.

How to solve

• It can be solved by (existing) bruteforce — enumerate all m^n assignments of n records to m sectors, compute the latency cost for each assignment, check if any achieves cost <= K.
• It can be solved by reducing to integer programming.
• Other: For fixed m, dynamic programming in pseudo-polynomial time. Greedy heuristic: assign records to sectors in decreasing order of probability, placing each record in the sector that minimizes incremental cost.

Example Instance

Instance 1 (YES, balanced allocation possible):
Records R = {r_1, r_2, r_3, r_4, r_5, r_6} with m = 3 sectors.
Probabilities: p(r_1) = 0.2, p(r_2) = 0.15, p(r_3) = 0.15, p(r_4) = 0.2, p(r_5) = 0.1, p(r_6) = 0.2.
Sum = 1.0 ✓.

Latency matrix for m = 3:

• d(1,1) = 2, d(1,2) = 0, d(1,3) = 1
• d(2,1) = 1, d(2,2) = 2, d(2,3) = 0
• d(3,1) = 0, d(3,2) = 1, d(3,3) = 2

Allocation: R_1 = {r_1, r_5} (p = 0.3), R_2 = {r_2, r_4} (p = 0.35), R_3 = {r_3, r_6} (p = 0.35).

Cost = sum_{i,j} p(R_i)p(R_j)d(i,j):
= p1p1d(1,1) + p1p2d(1,2) + p1p3d(1,3) + p2p1d(2,1) + p2p2d(2,2) + p2p3d(2,3) + p3p1d(3,1) + p3p2d(3,2) + p3p3d(3,3)
= 0.30.32 + 0.30.350 + 0.30.351 + 0.350.31 + 0.350.352 + 0.350.350 + 0.350.30 + 0.350.351 + 0.350.352
= 0.18 + 0 + 0.105 + 0.105 + 0.245 + 0 + 0 + 0.1225 + 0.245
= 1.0025

Set K = 1.01. Cost = 1.0025 <= 1.01. Answer: YES ✓

Instance 2 (NO, impossible to achieve low cost):
Records R = {r_1, r_2, r_3, r_4, r_5, r_6} with m = 3 sectors.
Probabilities: p(r_1) = 0.5, p(r_2) = 0.1, p(r_3) = 0.1, p(r_4) = 0.1, p(r_5) = 0.1, p(r_6) = 0.1.
Sum = 1.0 ✓.

The highly skewed distribution (r_1 has probability 0.5) makes it impossible to balance sectors evenly. Brute-force enumeration over all 3^6 = 729 assignments yields:

Optimal allocation: R_1 = {r_1} (p = 0.5), R_2 = {r_2, r_3, r_4} (p = 0.3), R_3 = {r_5, r_6} (p = 0.2).

Minimum achievable cost:
= 0.50.52 + 0.50.30 + 0.50.21 + 0.30.51 + 0.30.32 + 0.30.20 + 0.20.50 + 0.20.31 + 0.20.22
= 0.50 + 0 + 0.10 + 0.15 + 0.18 + 0 + 0 + 0.06 + 0.08
= 1.07

Set K = 0.5. Minimum cost = 1.07 > 0.5. Answer: NO ✓

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	Novel problem, but orphan node — no existing problem connects to it
Non-trivial	✅ Pass	Distinct circular latency objective with partition-based feasibility
Correctness	✅ Pass	References verified; complexity claims consistent with literature
Well-written	❌ Fail	Example 2 incomplete; variable encoding needs clarification for dims(); missing size field getters

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

The problem ExpectedRetrievalCost does not exist in the current codebase. It is a legitimate NP-complete problem from Garey & Johnson (SR4, p.227). However, the associated rules mention reduction from PARTITION/3-PARTITION — neither of which exists in the reduction graph. The target rule R098 mentions "Rooted Tree Storage Assignment" which also does not exist. This means the problem would be an orphan node with no connections to existing problems. The practical motivation (drum-like storage, rotational latency) is historically interesting but somewhat dated. Warn: adding this problem would be more valuable if paired with a reduction rule connecting it to an existing problem.

Non-trivial

This is a genuinely distinct problem. The circular latency function d(i,j) with modular arithmetic, combined with the probabilistic weighting p(R_i)*p(R_j), creates a unique objective that does not match any existing problem in the codebase. It is not a repackaging of BinPacking (different objective), nor of any graph problem (input is a probability distribution, not a graph). Pass.

Correctness

References verified:

• Cody and Coffman (1976): "Record allocation for minimizing expected retrieval costs on drum-like storage devices," Journal of the ACM 23(1):103-115 — confirmed via ACM Digital Library. The paper exists with correct authors (R. A. Cody and E. G. Coffman, Jr.), correct volume/pages, and addresses exactly this problem. An errata was also published in JACM 23(3):572.
• NP-completeness claim: The issue states NP-complete in the strong sense via reduction from 3-PARTITION, consistent with the Garey & Johnson entry which references [Cody and Coffman, 1976] with transformation from PARTITION.
• Latency function: The definition of d(i,j) matches the standard circular distance formulation. The example computation in Instance 1 is arithmetically correct.

Pass.

Well-written

Failures:

1. Example 2 is incomplete: The NO instance does not provide the actual minimum achievable cost. It states "The minimum achievable cost exceeds K" without computing it. A proper NO instance should either: (a) compute the optimal cost and show it exceeds K, or (b) provide a mathematical argument for infeasibility. The current text is a hand-wave.

2. Variable encoding for dims() is unclear: The Variables section says each variable x_r is in {1, ..., m}, which would give dims() = vec![m; n]. This is reasonable but should be stated explicitly. The current phrasing is indirect.

3. Missing size field getters: The Schema section does not specify getter methods needed for declare_variants!. Should include num_records() (returns n) and num_sectors() (returns m) at minimum.

4. Missing concrete complexity string: No expression suitable for declare_variants! is provided. For general m, something like "m ^ num_records" would be needed (or a tighter bound if one exists).

5. Bound type mismatch: The issue definition (from GJ) uses "positive integer K" but the Schema uses f64 for the bound. This inconsistency should be addressed — either use integer arithmetic (matching the original formulation with rational probabilities) or explicitly justify the f64 relaxation.

6. dims() encoding loses information: With dims() = vec![m; n], the brute-force solver would enumerate m^n configurations. Each configuration assigns records to sectors, which is correct. However, the evaluate function needs to compute the latency cost from this assignment, which requires aggregating probabilities by sector. This should be spelled out more clearly.

Recommendations

• Complete Example 2 with an actual cost computation showing the bound is exceeded
• Explicitly state dims() = vec![m; n] in the Variables section
• Add num_records() and num_sectors() as size field getters
• Resolve the integer vs. f64 type for the bound K
• Provide a concrete complexity string for declare_variants!

[isPANN]

Issue Quality Check — Model (Re-check)

Previously checked 2026-03-12. Issue body unchanged — same issues persist.

Check	Result	Details
Usefulness	✅ Pass	Novel problem; Partition exists in codebase, planned reduction has a valid endpoint
Non-trivial	✅ Pass	Distinct circular latency objective with partition-based feasibility
Correctness	✅ Pass	Cody & Coffman (1976) verified via ACM DL; complexity claims match GJ SR4
Well-written	❌ Fail	Example 2 incomplete; missing size field getters; missing complexity string; bound type inconsistency

Overall: 3 passed, 0 warnings, 1 failed

Previously: 2 passed, 1 warning, 1 failed → Now: 3 passed, 0 warnings, 1 failed (Usefulness upgraded from Warn to Pass since Partition now exists in the codebase as a valid reduction endpoint).

---

Usefulness

The problem ExpectedRetrievalCost does not exist in the current codebase. It is a legitimate NP-complete problem from Garey & Johnson (SR4, p.227). The issue mentions "R098: Partition / 3-Partition → Expected Retrieval Cost" as an associated rule. Partition exists in the reduction graph (currently isolated, but present), so the planned reduction has a valid source endpoint. This connection would benefit both problems. Pass.

Non-trivial

The circular latency function d(i,j) with modular arithmetic, combined with the probabilistic weighting p(R_i)·p(R_j), creates a unique objective that does not match any existing problem:

• Not BinPacking (capacity constraints vs. latency minimization)
• Not MultipleCopyFileAllocation (graph-based file placement, different objective)
• Not QuadraticAssignment (facility-location assignment, different distance/flow structure)
• Not Partition (two-way equal-sum partition vs. m-way latency-minimizing partition)

Pass.

Correctness

Reference verified:

• Cody and Coffman (1976): "Record allocation for minimizing expected retrieval costs on drum-like storage devices," Journal of the ACM 23(1):103-115. Confirmed via ACM Digital Library (DOI: 10.1145/321921.321933). Authors, title, volume, pages all match. Erratum in JACM 23(3):572.
• NP-completeness: Garey & Johnson list this as strongly NP-complete, transformation from PARTITION. Consistent with the issue's claims.
• Latency function: d(i,j) definition matches the standard circular distance formulation. Example 1 arithmetic independently verified (cost = 1.0025).
• Example 2: Independently verified via brute force — minimum achievable cost is 1.07, which exceeds K=0.5. The NO instance is valid.

Pass.

Recommendations

• Coffman, Johnson, and Leung (1978): "An efficient algorithm for allocating paged, drum-like storage," BIT Numerical Mathematics 18:52-66. Proposes improved heuristics — could be mentioned for approximation context.
• Cardonha, Cire, and Villa Real (2021/2025): Modern variant for linear cold storage with FPTAS results (arXiv:2112.07018). Interesting for context but different problem.

Well-written

Failures:

1. Example 2 incomplete — The NO instance states "The minimum achievable cost exceeds K" without computing the actual minimum. Brute-force verification shows the minimum cost is 1.07 (allocation: r₁→sector 1, {r₂,r₃,r₄}→sector 2, {r₅,r₆}→sector 3), but this must be shown in the issue.

2. Missing size field getters — The Schema section does not specify getter methods needed for declare_variants! and #[reduction(overhead)]. Must include at least num_records() (returns n = |R|) and num_sectors() (returns m).

3. Missing concrete complexity string — No expression suitable for declare_variants! is provided. For the brute-force algorithm, this should be something like "num_sectors ^ num_records" (or a tighter bound if one exists for the general case).

4. Bound type inconsistency — Garey & Johnson defines K as a "positive integer" but the Schema uses f64 for the bound field. Since the cost function involves products of rational probabilities × integer latencies, the cost is rational, not necessarily integer. The issue should either: (a) justify the f64 relaxation (the cost sum is rational, so integer K from GJ is a simplification), or (b) use integer types throughout with rational arithmetic. This is a design decision that should be explicitly addressed.

5. Complexity section missing concrete expression — The Complexity section discusses brute-force O(m^n · m²) but does not provide the required concrete complexity expression in terms of problem parameters (e.g., num_sectors^num_records).

Recommendations

• Complete Example 2 with the actual optimal cost computation (minimum = 1.07, best allocation = {r₁}→S₁, {r₂,r₃,r₄}→S₂, {r₅,r₆}→S₃)
• Add num_records() and num_sectors() as size field getters
• Add a concrete complexity string: "num_sectors ^ num_records" for brute-force
• Explicitly address the integer-vs-float decision for the bound K

[isPANN]

Fix-issue changelog

• Added explicit dims() specification (vec![m; n]) to Variables section
• Added Size field getters (num_records(), num_sectors()) to Schema section
• Added note explaining f64 relaxation of GJ's integer K bound
• Added Concrete complexity string "num_sectors ^ num_records" to Complexity section
• Completed Example 2 with full brute-force cost computation (minimum = 1.07, best allocation shown step by step)

Applied by /fix-issue.