2026/01/01 by David B. Shmoys, Varun Suriyanarayana, Seeun William Umboh · 1 voice
Computer Science · Decision Sciences · Engineering · #Auction Theory and Applications #Optimization and Search Problems #Scheduling and Optimization Algorithms
paper · doi:10.1137/1.9781611978971.100
openalex publication_date 2026/01/01 · openalex created_date 2026/01/08 · openalex updated_date 2026/07/29
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.