Fully Polynomial Time Approximation Schemes for stochastic dynamic programs

Nir Halman; Diego Klabjan; Chung Lun Li; James Orlin; David Simchi-Levi

Fully Polynomial Time Approximation Schemes for stochastic dynamic programs

Nir Halman, Diego Klabjan, Chung Lun Li, James Orlin, David Simchi-Levi

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

20 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages	700-709
Number of pages	10
Publication status	Published - 1 Dec 2008
Event	19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: 20 Jan 2008 → 22 Jan 2008

Conference

Conference	19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/Territory	United States
City	San Francisco, CA
Period	20/01/08 → 22/01/08

ASJC Scopus subject areas

Software
Mathematics(all)

Cite this

@inproceedings{5ccb346abbbc4560b34f2b559a1017d8,

title = "Fully Polynomial Time Approximation Schemes for stochastic dynamic programs",

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.",

author = "Nir Halman and Diego Klabjan and Li, {Chung Lun} and James Orlin and David Simchi-Levi",

year = "2008",

month = dec,

day = "1",

language = "English",

isbn = "9780898716474",

pages = "700--709",

booktitle = "Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "19th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 20-01-2008 Through 22-01-2008",

}

TY - GEN

T1 - Fully Polynomial Time Approximation Schemes for stochastic dynamic programs

AU - Halman, Nir

AU - Klabjan, Diego

AU - Li, Chung Lun

AU - Orlin, James

AU - Simchi-Levi, David

PY - 2008/12/1

Y1 - 2008/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=51849137610&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 9780898716474

SP - 700

EP - 709

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -

Fully Polynomial Time Approximation Schemes for stochastic dynamic programs

Abstract

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this