Greedy Caching Versus Exact Packing at the Edge
A streaming service pre-loads titles onto edge nodes before a live event. Each candidate title i has a size w_i in GB and a predicted value v_i in saved egress units. A representative node has 10 GB free. The catalog slice for that node has four hot titles: T1 (6 GB, 30 units), T2 (5 GB, 24 units), T3 (5 GB, 24 units) and T4 (3 GB, 9 units). The shipped loader sorts titles by value density v_i/w_i in descending order and inserts each one whose size still fits, never revisiting a decision. It chose T1 and T4 and the team signed off because the density ordering 'looked obviously right'. The same code runs at scale on the global origin, where n = 200 and capacity is expressed in bytes, roughly 5×10¹⁰. A junior engineer proposes replacing the heuristic with a dynamic program over capacity.
1. Show, with these four titles, that the density-ordered loader is not optimal. Give both packings and the value gap.
Read the worked answer
Densities: T1 = 30/6 = 5.0, T2 = 24/5 = 4.8, T3 = 24/5 = 4.8, T4 = 9/3 = 3.0. The loader visits in the order T1, T2, T3, T4.
T1 fits (6 of 10 GB, 30 units). T2 then needs 5 GB and only 4 remain, so it is skipped; T3 likewise; T4 needs 3 GB and fits, bringing the load to 9 GB and 39 units. Total: 39.
The optimum is T2 + T3 = 10 GB exactly, value 48. So the heuristic loses 9 units, about 19% of attainable value, on a four-item instance.
The mechanism is the failure mode of every greedy on a knapsack: taking the highest-density item consumes capacity that two slightly lower-density items would have used better. Density ordering is only optimal for the fractional relaxation, where T1 could be taken with 4/5 of T2. Integrality is exactly what breaks it. Note also that the gap is not monotone in the density ordering - the instance looks benign because T1's density advantage over T2 is only 4%.
2. Write the exact dynamic program for this node's 10 GB problem, state its complexity, and justify why it is exact.
Read the worked answer
Index items 1..n and capacities 0..C in whole GB. Let V[i][c] be the best value using a subset of the first i items with total size at most c.
Base: V[0][c] = 0. Transition: V[i][c] = V[i−1][c] if w_i > c, otherwise V[i][c] = max(V[i−1][c], v_i + V[i−1][c − w_i]). Answer: V[n][C]. Recover the subset by walking back and recording whether the second term was taken.
Complexity: O(nC) time and O(nC) space, reducible to O(C) space for the value alone - but reconstruction then needs either the full table or Hirschberg-style divide-and-conquer, so keep the table unless memory is tight. Here n = 60 and C = 10,000 MB gives 600,000 cells, trivially fast.
Why exact: the optimum either excludes item n (covered by V[n−1][C]) or includes it, in which case the remainder must be an optimal packing of the first n−1 items into C − w_n. That is optimal substructure, and induction on n proves the recurrence equals the true optimum. The DP never prunes a branch and never assumes density ordering, which is precisely what the greedy lacked.
3. The same loader must run on the origin with n = 200 and capacity about 5×10¹⁰ bytes. Is the DP viable there? What do you do instead?
Read the worked answer
No. O(nC) at n = 200 and C = 5×10¹⁰ units is about 10¹³ cells; at one byte per cell that is 10 TB. Even scaling capacity to MB leaves 5×10⁴ × 200 = 10⁷ cells, which is fine, but the scaling loses exactness unless all weights are multiples of 1 MB. Meet-in-the-middle is also out: 2^100 subsets per half is astronomical, and MITM only works to about n = 40.
Viable options, in the order I would try them:
- Branch and bound with a fractional-knapsack upper bound. Sort by density, depth-first, prune when the LP bound cannot beat the incumbent. On instances with 200 items and a capacity much larger than any single item, the bound is tight and this is usually near-instant, though worst case is exponential.
- Dynamic programming over total value, O(n·Σv), if the value range is smaller than the capacity range - this is the correct symmetry to exploit.
- An FPTAS: round each v_i to multiples of k = ε·v_max/n and run the capacity DP on the rounded values, giving (1−ε) optimality in O(n²/ε) time.
Given a pre-event planning job with minutes of budget, branch and bound plus an FPTAS fallback is the pragmatic answer; the greedy should be kept only as a fallback when the optimizer times out, and its gap monitored.