An FPTAS for the knapsack problem with parametric weights
From MaRDI portal
Publication:2294221
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
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
