Abstract:
Since its inception in the mid-60s, the inventory staggering problem has been explored and exploited in a wide range of application domains, such as production planning, stock control systems, warehousing, and aerospace/defense logistics. However, even with a rich history of academic focus, we are still very much in the dark when it comes to cornerstone computational questions around inventory staggering and to related structural characterizations, with our methodological toolbox being severely under-stocked.
The central contribution of this paper consists in devising a host of algorithmic techniques and analytical ideas — some being entirely novel and some leveraging well-studied concepts in combinatorics and number theory — for surpassing essentially all known approximation guarantees for the inventory staggering problem. In particular, our work demonstrates that numerous structural properties open the door for designing polynomial-time approximation schemes; these findings offer substantial improvements over currently available constant-factor approximations and resolve outstanding open questions in their respective contexts (Teo et al., 1998; Hum et al., 2005; Hochbaum and Rao, 2019, 2020).
In parallel, we develop new theory around a number of yet-uncharted questions, related to the sampling complexity of peak inventory estimation as well as to the plausibility of groupwise synchronization.
*************