An FPTAS for the knapsack problem with parametric weights

DOI10.1016/j.orl.2018.07.005zbMath1476.90282arXiv1703.06048OpenAlexW2604456416WikidataQ129558590 ScholiaQ129558590MaRDI QIDQ2294221

Michael Holzhauser, Nir Halman, Sven O. Krumke

Publication date: 10 February 2020

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

parametric optimizationapproximation algorithmsknapsack problems

Mathematics Subject Classification ID

Sensitivity, stability, parametric optimization (90C31) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (6)

Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ An approximation algorithm for a general class of parametric optimization problems ⋮ Integer knapsack problems with profit functions of the same value range ⋮ Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint ⋮ 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
• Approximation schemes for the parametric knapsack problem
• 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
• The inverse-parametric knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• An FPTAS for the parametric knapsack problem
• A note on the parametric maximum flow problem and some related reoptimization issues
• Complexity of some parametric integer and network programming problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Combinatorial Optimization with Rational Objective Functions
• 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

This page was built for publication: An FPTAS for the knapsack problem with parametric weights