On the complexity of energy storage problems

DOI10.1016/j.disopt.2017.11.001zbMath1506.90013OpenAlexW2777075140MaRDI QIDQ1662159

Giacomo Nannicini, Nir Halman, James B. Orlin

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1721.1/126466

zbMATH Keywords

dynamic programmingapproximation algorithmsenergy storage\(K\)-approximation sets

Mathematics Subject Classification ID

Stochastic programming (90C15) Inventory, storage, reservoirs (90B05) Dynamic programming (90C39)

Related Items (6)

Least squares policy iteration with instrumental variables vs. direct policy search: comparison against optimal benchmarks using energy storage ⋮ A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times ⋮ Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ A faster FPTAS for counting two-rowed contingency tables ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle
• Optimal Commodity Trading with a Capacitated Storage Asset
• A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
• PP is as Hard as the Polynomial-Time Hierarchy
• Discrete Convex Analysis
• Fully Polynomial Time Approximation Schemes for Stochastic Dynamic Programs
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• An Optimal Approximate Dynamic Programming Algorithm for Concave, Scalar Storage Problems With Vector-Valued Controls
• Decision and Horizon Rules for Stochastic Planning Problems: A Linear Example
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs
• Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella.

This page was built for publication: On the complexity of energy storage problems