A new fully polynomial time approximation scheme for the Knapsack problem
From MaRDI portal
Publication:1304384
DOI10.1023/A:1009813105532zbMath0957.90112OpenAlexW1524700731MaRDI QIDQ1304384
Hans Kellerer, Ulrich Pferschy
Publication date: 22 September 1999
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1009813105532
Related Items (35)
Multistage knapsack ⋮ Knapsack problem with objective value gaps ⋮ An FPTAS for the parametric knapsack problem ⋮ On a resource-constrained scheduling problem with application to distributed systems reconfiguration ⋮ 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 ⋮ A Polynomial-Time Approximation Scheme for Sequential Batch Testing of Series Systems ⋮ A new fully polynomial time approximation scheme for the interval subset sum problem ⋮ Reoptimizing the 0-1 knapsack problem ⋮ A faster FPTAS for the unbounded knapsack problem ⋮ Computing knapsack solutions with cardinality robustness ⋮ Unnamed Item ⋮ Approximability of Two Variants of Multiple Knapsack Problems ⋮ Learning-augmented algorithms for online subset sum ⋮ Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties ⋮ The symmetric quadratic knapsack problem: approximation and scheduling applications ⋮ An efficient fully polynomial approximation scheme for the Subset-Sum problem. ⋮ Minimum and worst-case performance ratios of rollout algorithms ⋮ Reductions between scheduling problems with non-renewable resources and knapsack problems ⋮ Order acceptance and scheduling with machine availability constraints ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Approximation algorithms for scheduling with reservations ⋮ An FPTAS for the knapsack problem with parametric weights ⋮ A Survey on Approximation Algorithms for Scheduling with Machine Unavailability ⋮ A successive approximation algorithm for the multiple knapsack problem ⋮ There is no EPTAS for two-dimensional knapsack ⋮ Approximation algorithms for knapsack problems with cardinality constraints ⋮ 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 ⋮ Two-machine shop scheduling: Compromise between flexibility and makespan value ⋮ Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem
This page was built for publication: A new fully polynomial time approximation scheme for the Knapsack problem
