Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
DOI10.1137/19M1308633OpenAlexW3211492119MaRDI QIDQ5013571FDOQ5013571
Authors: Tzvi Alon, Nir Halman 
Publication date: 1 December 2021
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1308633
Recommendations
- Strongly polynomial FPTASes for monotone dynamic programs
- Fully polynomial time approximation schemes for stochastic dynamic programs
- A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
- A computationally efficient FPTAS for convex stochastic dynamic programs
- Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states
Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Stochastic programming (90C15) Approximation algorithms (68W25) Inventory, storage, reservoirs (90B05) Transportation, logistics and supply chain management (90B06) Markov and semi-Markov decision processes (90C40) Derivative-free methods and methods using generalized derivatives (90C56)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs
- A deterministic polynomial-time approximation scheme for counting knapsack solutions
- Algorithms for Scheduling Independent Tasks
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- The Recognition of Series Parallel Digraphs
- Sampling-based approximation algorithms for multistage stochastic optimization
- A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
- A fully polynomial-time approximation scheme for single-item stochastic inventory control with discrete demand
- Fully polynomial time approximation schemes for stochastic dynamic programs
- Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks
- The logic of logistics. Theory, algorithms, and applications for logistics management
- Approximation schemes for a class of subset selection problems
- Title not available (Why is that?)
- Scheduling deteriorating jobs to minimize makespan
- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
- An Efficient Algorithm for the Multiperiod Capacity Expansion of One Location in Telecommunications
- Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
- Approximating the nonlinear newsvendor and single-item stochastic lot-sizing problems when data is given by an oracle
- On the complexity of energy storage problems
- The TV advertisements scheduling problem
- A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times
- Bi-criteria path problem with minimum length and maximum survival probability
- Faster FPTASes for counting and random generation of knapsack solutions
- Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States
- A faster FPTAS for \#Knapsack
- Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs
Cited In (2)
This page was built for publication: Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5013571)
