arXiv preprint ·
Improved Approximation Guarantees for Periodic-Review Stochastic Inventory Control
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In periodic-review stochastic inventory control, replenishment policies must balance holding and backlogging costs while responding to uncertain demands and evolving forecasts that may be arbitrarily correlated and nonstationary. In this general information setting, Levi, P{á}l, Roundy, and Shmoys (Mathematics of Operations Research 2007) established that the fully adaptive optimum can be approximated within factor $2$, which had remained the best-known performance guarantee since then. Their marginal cost accounting and dual-balancing framework made this comparison possible without computing optimal decisions across future trajectories, opening a broad research program on approximation algorithms for stochastic inventory systems. We break this long-standing barrier for periodic-review stochastic inventory control, showing how to compete against the fully adaptive benchmark within factor $\frac{ e }{ e-1 } \approx 1.582$ while retaining general demand correlations and evolving forecasts. We attain these advances by discovering a structural connection between marginal inventory accounting and weighted stopping problems, where each unit's conditional holding charge forms a supermartingale, while postponing its order incurs a history-dependent backlog charge. To leverage the random thresholding approach of Ma and Tzamos (ICML 2023) in this context, we develop a potential-function analysis, leading to an $\frac{ e }{ e-1 }$-approximation with respect to any unit's stopping problem. Subsequently, our common-threshold policy coordinates these marginal decisions into a global replenishment policy without additional loss.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Local Budget Benefits, Population Commitment, and Solver Performance: A DGO Case Study with Controlled DE Transfer
Non-asymptotic analysis of SGLD with discontinuous stochastic gradients: a new route to portfolio CVaR minimization
Quantum Vehicle Routing Problem: a smart initialization strategy for ill-conditioned optimization landscapes
Conic Certification of Transformer Attention
Stochastic Mirror Descent under Dependent Observations
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.