Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
David B. Shmoys, Varun Suriyanarayana, Seeun William Umboh · Society for Industrial and Applied Mathematics eBooks · 2026
The Joint Replenishment Problem (JRP) is a classical inventory management problem, that aims to model the trade-off between coordinating orders for multiple commodities (and their cost) with holding costs incurred by meeting demand in advance. Recently, Moseley, Niaparast and Ravi introduced a natural online generalization of the JRP in which inventory corresponding to demands may be replenished late, for a delay cost, or early, in which case there is a holding cost associated with storing it until the desired service time. They established that when the holding and delay costs are monotone and uniform across demands, there is a 30-competitive algorithm that employs a greedy strategy and a dual-fitting based analysis; notably, they left relaxing the uniformity assumption as an open problem. This assumption is a significant limitation, and in fact, remarkable from the perspective that most online problems with only delay costs do not require uniformity, only monotonicity.