An FPTAS for the knapsack problem with parametric weights

DOI10.1016/J.ORL.2018.07.005MaRDI QIDQ2294221zbMATH OpenOpenAlexWikidataFDO

Authors Nir Halman, Michael Holzhauser, 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

approximation algorithmsknapsack problemsparametric optimization

Mathematics Subject Classification ID

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

Abstract: In this paper, we investigate the parametric weight knapsack problem, in which the item weights are affine functions of the form $w_i(lambda)=a_i+lambdacdot{b}_i$ for $iin1,ldots,n$ depending on a real-valued parameter $lambda$. 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 the first 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. Our FPTAS is based on two different approaches and achieves a running time of $mathcalO(n^3/varepsilo{n}^{2}cdotminlo{g}^{2}P,n^{2}cdotminlogM,nlog(n/varepsilon)/log(nlog(n/varepsilon)))$ where $P$ is an upper bound on the optimal profit and $M:=maxW,ncdotmax{a}_i,b_i:iin1,ldots,n$ for a knapsack with capacity $W$.

Recommendations

• An FPTAS for the parametric knapsack problem
• Improved dynamic programming in connection with an FPTAS for the knapsack problem
• Knapsack problems: a parameterized point of view
• Approximation schemes for the parametric knapsack problem
• A faster FPTAS for knapsack problem with cardinality constraint
• A faster FPTAS for knapsack problem with cardinality constraint
• A faster FPTAS for \#Knapsack
• Implementing an efficient fptas for the 0-1 multi-objective knapsack problem

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
• An FPTAS for the parametric knapsack problem
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Approximation schemes for the parametric knapsack problem
• Combinatorial Optimization with Rational Objective Functions
• 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 the Knapsack and Sum of Subset Problems
• Faster parametric shortest path and minimum‐balance algorithms
• 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?)
• 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
• The inverse-parametric knapsack problem

Cited in

(10)

• 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 parametric knapsack problem
• Approximation schemes for the parametric knapsack problem
• A faster FPTAS for knapsack problem with cardinality constraint
• 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
• A survey of exact and approximation algorithms for linear-parametric optimization problems

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

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