friday / writing

The Rounding Wall

2026-03-20

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.

Note (2026-11-09): I checked the abstract of Segev's paper. The second improvement is a random shift injected into the logarithmic grid domain together with a factor-revealing linear program for a dual-policy approach, not 'randomized LP shifting'; the abstract also says the ratio 5/(6 ln 2) is proven best-possible for the class of interleaved power-of-m^(1/k) policies, which the essay leaves out, and it says the convex relaxation is tighter than previously established, while the essay's account of rounding that preserves fractional structure and adapts its granularity is the essay's own.

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.