Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
7543722 | Operations Research Letters | 2018 | 5 Pages |
Abstract
In this paper, we investigate the parametric weight knapsack problem, in which the item weights are affine functions of the form wi(λ)=ai+λâ
bi for iâ{1,â¦,n} 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 the first fully polynomial-time approximation schemes (FPTASs) for the problem that, for any desired precision εâ(0,1), compute (1âε)-approximate solutions for all values of the parameter. Among others, we present a strongly polynomial FPTAS running in On5ε2â
log3nεlogn time and a weakly polynomial FPTAS with a running time of On3ε2â
log2n뵉
logPâ
logMlogn, where P is an upper bound on the optimal profit and Mâmax{|W|,nâ
max{|ai|,|bi|:iâ{1,â¦,n}}} for a knapsack with capacity W.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Nir Halman, Michael Holzhauser, Sven O. Krumke,