Name
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.orl.2018.07.005 | Operations Research Letters |
Keywords | Field | DocType |
Knapsack problems,Parametric optimization,Approximation algorithms | Affine transformation,Binary logarithm,Combinatorics,Exponential function,Exact algorithm,Polynomial,Upper and lower bounds,Continuous knapsack problem,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
46 | 5 | 0167-6377 |
Citations | PageRank | References |
2 | 0.37 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nir Halman | 1 | 134 | 11.88 |
| Michael Holzhauser | 2 | 13 | 3.34 |
| Sven O. Krumke | 3 | 308 | 36.62 |