Abstract: Lost sales inventory models with large lead times, which arise in many practical settings, are notoriously difficult to optimize due to the curse of dimensionality. In this talk we show that when lead times are large, a very simple constant-order policy, first studied by Reiman, performs nearly optimally. The main insight of our work is that when the lead time is very large, such a significant amount of randomness is injected into the system between when an order for more inventory is placed and when that order is received, that ``being smart" algorithmically provides almost no benefit. Our main proof technique combines a novel coupling for suprema of random walks with arguments from queueing theory (this is joint work with Dmitriy A. Katz-Rogozhnikov, Yingdong Lu, Mayank Sharma, and Mark S. Squillante from IBM T.J. Watson Research Center).
