A faster FPTAS for the unbounded knapsack problem

DOI10.1016/j.ejc.2017.07.016zbMath1381.90071arXiv1504.04650OpenAlexW2751193914MaRDI QIDQ1678097

Klaus Jansen, Stefan E. J. Kraft

Publication date: 14 November 2017

Published in: Lecture Notes in Computer Science, European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.04650

zbMATH Keywords

polynomial time approximationUnbounded Knapsack Problem, approximation schemes

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (9)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ A note on a variant of the online open end bin packing problem ⋮ A faster FPTAS for the unbounded knapsack problem ⋮ Unnamed Item ⋮ Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties ⋮ Unnamed Item ⋮ Fully dynamic bin packing revisited ⋮ A faster FPTAS for knapsack problem with cardinality constraint ⋮ An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the Kenyon-Remila strip-packing algorithm
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• An efficient fully polynomial approximation scheme for the Subset-Sum problem.
• A faster FPTAS for the unbounded knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Approximate Max-Min Resource Sharing for Structured Concave Optimization
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Saving space by algebraization
• APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS
• An Improved Approximation Scheme for Variable-Sized Bin Packing
• A Linear Programming Approach to the Cutting-Stock Problem
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• An Improved Knapsack Solver for Column Generation
• Fast Asymptotic FPTAS for Packing Fragmentable Items with Costs
• Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications

This page was built for publication: A faster FPTAS for the unbounded knapsack problem