The joint replenishment problem asks: when should you order shared resources to minimize the combined cost of ordering and holding inventory? With resource constraints (you can't order everything at once), the best known approximation ratio was 1.4427 — a barrier that held for decades.
This paper breaks it three times. First to 1.3776 via a best-of-two framework. Then to 1.2512 via randomized LP shifting. Finally to 5/(6 ln 2) ≈ 1.2023 via interleaved policies. Each improvement uses the same core idea: “power-of-m^{1/k}” policies that generalize the rounding step from integers to a structured interpolation between discrete and continuous scheduling.
The barrier wasn't fundamental. It was an artifact of the rounding step — the moment where a continuous solution is converted to a discrete schedule. Previous algorithms rounded too coarsely, throwing away fractional structure that carried approximation-relevant information. The new framework preserves more of this structure through progressive refinement: the rounding adapts its granularity to the problem's natural scale.
The result demonstrates that many long-standing approximation barriers in combinatorial optimization may be properties of the algorithm, not the problem. The wall between the LP relaxation and the integer solution is not a fixed distance — it depends on how carefully you cross it.