A Caltech Library Service

A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand

Halman, Nir and Klabjan, Diego and Mostagir, Mohamed and Orlin, Jim and Simchi-Levi, David (2009) A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand. Mathematics of Operations Research, 34 (3). pp. 674-685. ISSN 0364-765X.

[img] PDF - Published Version
Restricted to Repository administrators only
See Usage Policy.


Use this Persistent URL to link to this item:


The single-item stochastic inventory control problem is to find an inventory replenishment policy in the presence of independent discrete stochastic demands under periodic review and finite time horizon. In this paper, we prove that this problem is intractable and design for it a fully polynomial-time approximation scheme.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:Copyright © 2009 by INFORMS. Received March 10, 2006; revised July 23, 2007, June 30, 2008, and March 3, 2009. Published online in Articles in Advance August 6, 2009. The authors thank the referees for their detailed comments, which helped us to improve the presentation of this paper considerably. They thank Retsef Levi for pointing out that our original proof of #P-hardness for stochastic inventory control also implies the #P-hardness of evaluating cdfs for convolutions of discrete variables. Last, the authors thank Oded Goldreich for inspiring discussions and Leslie Ann Goldberg for pointing out references. The first, second, third, and fifth authors were supported by ONR Contracts N00014-95-1-0232 and N00014-01-1-0146; NSF Contracts DMI-0085683 and DMI-0245352; and by the NASA interplanetary supply chain and logistics architectures project. The fourth author was supported in part by ONR Grant N000140810029. The first, fourth, and fifth authors were also supported by NSF Contract CMMI-0758069. MSC2000 subject classification: Primary: 90B05, 90C39, 68W25; secondary: 90C15, 90C25, 49M25 OR/MS subject classification: Primary: inventory/production; approximations/heuristics; secondary: production/scheduling; approximations/heuristics
Funding AgencyGrant Number
Office of Naval ResearchN00014-95-1-0232
Office of Naval ResearchN00014-01-1-0146
Office of Naval ResearchN000140810029
Subject Keywords:stochastic inventory management; approximation algorithms; stochastic dynamic programming
Issue or Number:3
Record Number:CaltechAUTHORS:20090911-153600795
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:15802
Deposited By: George Porter
Deposited On:29 Sep 2009 17:07
Last Modified:03 Oct 2019 01:03

Repository Staff Only: item control page