Strongly Polynomial FPTASes for Monotone Dynamic Programs
- 2 June 2022
- journal article
- research article
- Published by Springer Nature in Algorithmica
- Vol. 84 (10) , 2785-2819
Abstract
No abstract availableKeywords
Funding Information
- Israel Science Foundation (399/17)
- United States - Israel Binational Science Foundation (2018095)
- Israel Science Foundation
- Israel Science Foundation (1074/21)
This publication has 24 references indexed in Scilit:
- A General Framework for Designing Approximation Schemes for Combinatorial Optimization Problems with Many Objectives Combined into OneOperations Research, 2013
- A generic FPTAS for partition type optimisation problemsInternational Journal of Planning and Scheduling, 2012
- A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack SolutionsSIAM Journal on Computing, 2012
- A faster strongly polynomial time algorithm for submodular function minimizationMathematical Programming, 2007
- Approximation schemes for a class of subset selection problemsTheoretical Computer Science, 2007
- Improved Dynamic Programming in Connection with an FPTAS for the Knapsack ProblemJournal of Combinatorial Optimization, 2004
- Scheduling deteriorating jobs to minimize makespanNaval Research Logistics (NRL), 1998
- Linear Programming in Linear Time When the Dimension Is FixedJournal of the ACM, 1984
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956