Improved dynamic programming in connection with an FPTAS for the knapsack problem

DOI10.1023/B:JOCO.0000021934.29833.6BzbMath1058.90070OpenAlexW2081136687WikidataQ61638367 ScholiaQ61638367MaRDI QIDQ1768594

Ulrich Pferschy, Hans Kellerer

Publication date: 15 March 2005

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/b:joco.0000021934.29833.6b

zbMATH Keywords

dynamic programmingknapsack problemfully polynomial approximation scheme

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) Boolean programming (90C09) Approximation algorithms (68W25)

Related Items (29)

An FPTAS for the parametric knapsack problem ⋮ A new class of hard problem instances for the 0-1 knapsack problem ⋮ Exact solution of the robust knapsack problem ⋮ Approximation schemes for non-separable non-linear Boolean programming problems under nested knapsack constraints ⋮ Reoptimizing the 0-1 knapsack problem ⋮ A faster FPTAS for the unbounded knapsack problem ⋮ Unnamed Item ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ On approximating the incremental knapsack problem ⋮ An efficient fully polynomial approximation scheme for the Subset-Sum problem. ⋮ Minimum and worst-case performance ratios of rollout algorithms ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates ⋮ Solutions for subset sum problems with special digraph constraints ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Algorithms for the bounded set-up knapsack problem ⋮ A new effective dynamic program for an investment optimization problem ⋮ Algorithms for communication scheduling in data gathering network with data compression ⋮ Order acceptance and scheduling with machine availability constraints ⋮ Unnamed Item ⋮ Communication scheduling in data gathering networks of heterogeneous sensors with data compression: algorithms and empirical experiments ⋮ An FPTAS for the knapsack problem with parametric weights ⋮ There is no EPTAS for two-dimensional knapsack ⋮ Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval ⋮ An approximation algorithm for a general class of multi-parametric optimization problems ⋮ Strongly polynomial FPTASes for monotone dynamic programs ⋮ Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems ⋮ Approximation schemes for multiperiod binary knapsack problems ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

This page was built for publication: Improved dynamic programming in connection with an FPTAS for the knapsack problem