An FPTAS for the parametric knapsack problem

DOI10.1016/J.IPL.2017.06.006MaRDI QIDQ2361499zbMATH OpenOpenAlexFDO

Authors Michael Holzhauser, Sven O. Krumke

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

approximation algorithmsknapsack problemsparametric optimization

Mathematics Subject Classification ID

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

Abstract: In this paper, we investigate the parametric knapsack problem, in which the item profits are affine functions depending on a real-valued parameter. The aim is to provide a solution for all values of the parameter. It is well-known that any exact algorithm for the problem may need to output an exponential number of knapsack solutions. We present a fully polynomial-time approximation scheme (FPTAS) for the problem that, for any desired precision $varepsilonin(0,1)$, computes $(1-varepsilon)$-approximate solutions for all values of the parameter. This is the first FPTAS for the parametric knapsack problem that does not require the slopes and intercepts of the affine functions to be non-negative but works for arbitrary integral values. Our FPTAS outputs $mathcalO(frac{n}^{2}varepsilon)$ knapsack solutions and runs in strongly polynomial-time $mathcalO(frac{n}^{4}varepsilo{n}^2)$. Even for the special case of positive input data, this is the first FPTAS with a strongly polynomial running time. We also show that this time bound can be further improved to $mathcalO(frac{n}^{2}varepsiloncdotA(n,varepsilon))$, where $A(n,varepsilon)$ denotes the running time of any FPTAS for the traditional (non-parametric) knapsack problem.

Recommendations

• An FPTAS for the knapsack problem with parametric weights
• Approximation schemes for the parametric knapsack problem
• The inverse-parametric knapsack problem
• A faster FPTAS for knapsack problem with cardinality constraint

Cites work

• A Fast Parametric Maximum Flow Algorithm and Applications
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• A new fully polynomial time approximation scheme for the Knapsack problem
• A note on the parametric maximum flow problem and some related reoptimization issues
• Approximation schemes for the parametric knapsack problem
• Combinatorial optimization. Networks and matroids
• Complexity of some parametric integer and network programming problems
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Faster parametric shortest path and minimum‐balance algorithms
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 1002204 (Why is no real title available?)
• scientific article; zbMATH DE number 1830735 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Parametric shortest path algorithms with an application to cyclic staffing
• Parametric Solution for Linear Bicriteria Knapsack Models

Cited in

(13)

• A PTAS for the time-invariant incremental knapsack problem
• An approximation algorithm for a general class of multi-parametric optimization problems
• An FPTAS for the -modular multidimensional knapsack problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• An approximation algorithm for a general class of parametric optimization problems
• An FPTAS for the knapsack problem with parametric weights
• Approximation schemes for the parametric knapsack problem
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• A faster FPTAS for knapsack problem with cardinality constraint
• Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint
• A stronger lower bound on parametric minimum spanning trees
• A survey of exact and approximation algorithms for linear-parametric optimization problems
• A stronger lower bound on parametric minimum spanning trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2361499)