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 sets of computational rules, namely, the calc...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109135 https://orcid.org/0000-0002-7488-094X https://orcid.org/0000-0002-4650-1519 |
| _version_ | 1811096131094970368 |
|---|---|
| author | Halman, Nir Klabjan, Diego Li, Chung-Lun Orlin, James B Simchi-Levi, David |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Halman, Nir Klabjan, Diego Li, Chung-Lun Orlin, James B Simchi-Levi, David |
| author_sort | Halman, Nir |
| collection | MIT |
| description | 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 sets of computational rules, namely, the calculus of K-approximation functions and the calculus of K-approximation sets. Using our framework, we provide the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed. |
| first_indexed | 2024-09-23T16:38:20Z |
| format | Article |
| id | mit-1721.1/109135 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:38:20Z |
| publishDate | 2017 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/1091352022-10-03T07:20:52Z Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs Halman, Nir Klabjan, Diego Li, Chung-Lun Orlin, James B Simchi-Levi, David Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Massachusetts Institute of Technology. Institute for Data, Systems, and Society Sloan School of Management Orlin, James B Simchi-Levi, David 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 sets of computational rules, namely, the calculus of K-approximation functions and the calculus of K-approximation sets. Using our framework, we provide the first FPTASs for several NP-hard problems in various fields of research such as knapsack models, logistics, operations management, economics, and mathematical finance. Extensions of our framework via the use of the newly established computational rules are also discussed. 2017-05-17T13:53:29Z 2017-05-17T13:53:29Z 2014-10 2013-06 Article http://purl.org/eprint/type/JournalArticle 0895-4801 1095-7146 http://hdl.handle.net/1721.1/109135 Halman, Nir; Klabjan, Diego; Li, Chung-Lun; Orlin, James and Simchi-Levi, David. “Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs.” SIAM Journal on Discrete Mathematics 28, no. 4 (January 2014): 1725–1796. © 2014 Society for Industrial and Applied Mathematics https://orcid.org/0000-0002-7488-094X https://orcid.org/0000-0002-4650-1519 en_US http://dx.doi.org/10.1137/130925153 SIAM Journal on Discrete Mathematics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Halman, Nir Klabjan, Diego Li, Chung-Lun Orlin, James B Simchi-Levi, David Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| title | Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| title_full | Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| title_fullStr | Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| title_full_unstemmed | Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| title_short | Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs |
| title_sort | fully polynomial time approximation schemes for stochastic dynamic programs |
| url | http://hdl.handle.net/1721.1/109135 https://orcid.org/0000-0002-7488-094X https://orcid.org/0000-0002-4650-1519 |
| work_keys_str_mv | AT halmannir fullypolynomialtimeapproximationschemesforstochasticdynamicprograms AT klabjandiego fullypolynomialtimeapproximationschemesforstochasticdynamicprograms AT lichunglun fullypolynomialtimeapproximationschemesforstochasticdynamicprograms AT orlinjamesb fullypolynomialtimeapproximationschemesforstochasticdynamicprograms AT simchilevidavid fullypolynomialtimeapproximationschemesforstochasticdynamicprograms |