research-article

Fully polynomial time approximation schemes for stochastic dynamic programs

Authors:

David Simchi-LeviAuthors Info & Claims

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 700 - 709

Published: 20 January 2008 Publication History

Abstract

We develop a framework for obtaining (deterministic) Fully Polynomial Time Approximation Schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. Using our framework, we give the first FPTASs for several NP-hard problems in various fields of research such as knapsack-related problems, logistics, operations management, economics, and mathematical finance.

References

[1]

J. Adda and R. Cooper. Dynamic Economics: Quantitive Methods and Applications. MIT Press, 2003.

[2]

M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi. Towards a model for backtracking and dynamic programming. In Proceedings of the 20th IEEE Conference on Computational Complexity, 2005.

Digital Library

[3]

G. Ausiello, P, Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and Approximation. Springer, 1999.

Digital Library

[4]

A. Bandyopadhyay and D. Gamarnik. Counting without sampling, new algorithms for enumeration problems using statistical physics. To Appear in Random Structures and Algorithms, 2007.

[5]

M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali. Simple deterministic approximation algorithms for counting matchings. In Proceedings of the 39th ACM Symposium on Theory of Computing, 2007.

Digital Library

[6]

R. Bellman. Applied Dynamic Programming. Princeton University MIT Press, Princeton, NJ, 1957.

[7]

D. P. Bertsekas. Dynamic Programming and Optimal Control. Athena Scientific, Belmont, MA, 1995.

Digital Library

[8]

T. C. E. Cheng, Z.-L. Chen, C.-L. Li, and B. M.-T. Lin. Scheduling to minimize the total compression and late costs. Naval Research Logistics, 45:67--82, 1998.

[9]

B. C. Dean, M. X. Goemans, and J. Vondrák. Approximating the stochastic knapsack problem: the benefit of adaptivity. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004.

Digital Library

[10]

M. Dyer. Approximate counting by dynamic programming. In Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, pages 693--699, 2003.

Digital Library

[11]

M. Dyer, A. Frieze, and M. Jerrum. Approximately counting Hamilton paths and cycles in dense graphs. SIAM Journal on Computing, 27:1262--1272, 1998.

Digital Library

[12]

M. Dyer, L. A. Goldberg, C. Greenhill, and M. Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38:471--500, 2003.

[13]

D. Gamarnik and D. Katz. Correlation decay and deterministic fptas for counting list-colorings of a graph. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, 2007.

Digital Library

[14]

N. Halman, D. Klabjan, M. Mostagir, J. Orlin, and D. Simchi-Levi. A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Technical report, Massachusetts Institute of Technology, 2006. Submitted for journal publication.

[15]

K. Hinderer and K.-H. Waldmann. Cash management in a randomly varying environment. European Journal of Operational Research, 130:468--485, 2001.

[16]

D. S. Hochbaum. A nonlinear knapsack problem. Operations Research Letters, 17:103--110, 1995.

Digital Library

[17]

D. S. Hochbaum. Various notions of approximations: Good, better, best, and more. In D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, pages 346--398. PWS Publishing company, 1997.

Digital Library

[18]

E. Horowitz and S. Sahni. Exact and approximate algorithms for scheduling nonidentical processors. Journal of the ACM, 23:317--327, 1976.

Digital Library

[19]

O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22:463--468, 1975.

Digital Library

[20]

M. Jerrum and A. Sinclair. Approximating the permanent. SIAM Journal on Computing, 18:1149--1178, 1989.

Digital Library

[21]

M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM, 51(4):671--697, 2004.

Digital Library

[22]

R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, New York, 1972.

[23]

H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springler-Verlag, 2004.

[24]

M. Mihail and P. Winkler. On the number of Eulerian orientations of a graph. Algorithmica, 16:402--414, 1995.

[25]

K. P. Papadaki and W. B. Powell. An adaptive dynamic programming algorithm for stochastic multiproduct batch dispatch problem. Naval Research Logistics, 50:742--769, 2003.

[26]

E. Phelps. The accumulation of risky capital: A sequential utility analysis. Econometrica, 30:729--743, 1962.

[27]

H. Safer and J. Orlin. Fast approximation schemes for multi-criteria flow, knapsack, and scheduling problems. Sloan school working paper 3757--95, Massachusetts Institute of Technology, 1995.

[28]

S. Sahni. Algorithms for scheduling independent tasks. Journal of the ACM, 23:116--127, 1976.

Digital Library

[29]

I. Saniee. An efficient algorithm for the multiperiod capacity expansion of one location in telecommunications. Operations Research, 43:187--190, 1995.

[30]

V. J. Vazirani. Approximation Algorithms. Springler-Verlag, 2001.

Digital Library

[31]

D. Weitz. Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006.

Digital Library

[32]

G. J. Woeginger. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing, 12:57--75, 2000.

Digital Library

Cited By

Goyal VLevi RSegev D(2016)Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic DemandOperations Research10.1287/opre.2015.145064:1(219-235)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1287/opre.2015.1450
Mu SLyu YMorihata A(2015)Approximate by thinningScience of Computer Programming10.1016/j.scico.2014.07.00198:P4(484-515)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.scico.2014.07.001
Halman NOrlin JSimchi-Levi D(2012)Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an OracleOperations Research10.1287/opre.1110.103160:2(429-446)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1287/opre.1110.1031
Show More Cited By

Index Terms

Fully polynomial time approximation schemes for stochastic dynamic programs

Recommendations

Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs

We present a framework for obtaining fully polynomial time approximation schemes (FPTASs) for stochastic univariate dynamic programs with either convex or monotone single-period cost functions. This framework is developed through the establishment of two ...
Polynomial time approximation schemes and parameterized complexity

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP ...
Parameterized complexity and polynomial-time approximation schemes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '08: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms

January 2008

1289 pages

Program Chair:
Shang-Hua Teng
Boston University and Akamai Technologies, Inc.

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 20 January 2008

Check for updates

Qualifiers

Research-article

Conference

SODA08

Sponsor:

SIGACT

SODA08: 19th ACM-SIAM Symposium on Discrete Algorithms

January 20 - 22, 2008

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
349
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Goyal VLevi RSegev D(2016)Near-Optimal Algorithms for the Assortment Planning Problem Under Dynamic Substitution and Stochastic DemandOperations Research10.1287/opre.2015.145064:1(219-235)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1287/opre.2015.1450
Mu SLyu YMorihata A(2015)Approximate by thinningScience of Computer Programming10.1016/j.scico.2014.07.00198:P4(484-515)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.scico.2014.07.001
Halman NOrlin JSimchi-Levi D(2012)Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an OracleOperations Research10.1287/opre.1110.103160:2(429-446)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1287/opre.1110.1031
Bhalgat AGoel AKhanna SRandall D(2011)Improved approximation results for stochastic knapsack problemsProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133163(1647-1665)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133163
Mu SLyu YMorihata AOliveira BZalewski M(2010)Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinningProceedings of the 6th ACM SIGPLAN workshop on Generic programming10.1145/1863495.1863508(97-108)Online publication date: 26-Sep-2010
https://dl.acm.org/doi/10.1145/1863495.1863508
Bringmann KFriedrich T(2010)Approximating the volume of unions and intersections of high-dimensional geometric objectsComputational Geometry: Theory and Applications10.1016/j.comgeo.2010.03.00443:6-7(601-610)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.comgeo.2010.03.004
Halman NLi CSimchi-Levi D(2008)Fully Polynomial Time Approximation Schemes for Time-Cost Tradeoff Problems in Series-Parallel Project NetworksProceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques10.1007/978-3-540-85363-3_8(91-103)Online publication date: 25-Aug-2008
https://dl.acm.org/doi/10.1007/978-3-540-85363-3_8

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents