An FPTAS for the parametric knapsack problem

DOI10.1016/j.ipl.2017.06.006zbMath1407.68548arXiv1701.07822OpenAlexW2581390335MaRDI QIDQ2361499

Sven O. Krumke, Michael Holzhauser

Publication date: 30 June 2017

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

parametric optimizationapproximation algorithmsknapsack problems

Mathematics Subject Classification ID

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

Related Items

A stronger lower bound on parametric minimum spanning trees, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, An approximation algorithm for a general class of parametric optimization problems, Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint, A stronger lower bound on parametric minimum spanning trees, An FPTAS for the knapsack problem with parametric weights, An approximation algorithm for a general class of multi-parametric optimization problems, An FPTAS for the \(\varDelta \)-modular multidimensional knapsack problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation schemes for the parametric knapsack problem
• Finding the upper envelope of n line segments in O(n log n) time
• Parametric shortest path algorithms with an application to cyclic staffing
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• A note on the parametric maximum flow problem and some related reoptimization issues
• Complexity of some parametric integer and network programming problems
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Parametric Solution for Linear Bicriteria Knapsack Models
• A Fast Parametric Maximum Flow Algorithm and Applications
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• Faster parametric shortest path and minimum‐balance algorithms