Strongly polynomial FPTASes for monotone dynamic programs

DOI10.1007/s00453-022-00954-8OpenAlexW4281710052MaRDI QIDQ2088581

Nir Halman, Tzvi Alon

Publication date: 6 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-00954-8

zbMATH Keywords

dynamic programmingstrongly polynomial algorithms\(K\)-approximation sets and functions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Knapsack problems with position-dependent item weights or profits

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy
• A faster strongly polynomial time algorithm for submodular function minimization
• Geometric algorithms and combinatorial optimization.
• 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
• Improved dynamic programming in connection with an FPTAS for the knapsack 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
• A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand
• Linear Programming in Linear Time When the Dimension Is Fixed
• 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
• A Faster FPTAS for #Knapsack
• Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier
• 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

This page was built for publication: Strongly polynomial FPTASes for monotone dynamic programs