Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
From MaRDI portal
Publication:5013571
DOI10.1137/19M1308633OpenAlexW3211492119MaRDI QIDQ5013571
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
Analysis of algorithms and problem complexity (68Q25) Derivative-free methods and methods using generalized derivatives (90C56) Stochastic programming (90C15) Transportation, logistics and supply chain management (90B06) Approximation methods and heuristics in mathematical programming (90C59) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40) Approximation algorithms (68W25)
Related Items
Knapsack problems with position-dependent item weights or profits, Strongly polynomial FPTASes for monotone dynamic programs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
- Fully polynomial-time approximation schemes for time-cost tradeoff problems in series-parallel project networks
- A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs
- Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints
- 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
- Approximation schemes for a class of subset selection problems
- Faster FPTASes for counting and random generation of knapsack solutions
- The Logic of Logistics
- A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
- Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle
- Sampling-Based Approximation Algorithms for Multistage Stochastic Optimization
- A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
- The Recognition of Series Parallel Digraphs
- Algorithms for Scheduling Independent Tasks
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Scheduling deteriorating jobs to minimize makespan
- When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?
- Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States
- An Efficient Algorithm for the Multiperiod Capacity Expansion of One Location in Telecommunications
- A Faster FPTAS for #Knapsack
- Provably Near-Optimal Approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs
- Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into One
