Sensitivity analysis for knapsack problems: Another negative result. (English) Zbl 0957.90124
Summary: We answer a question of C. Blair [Discrete Appl. Math. 81, 133-139 (1998; Zbl 0895.90155)] on the computational complexity of a problem related to the so-called adjacent knapsack problems. We prove that this problem is DP-hard; hence, the problem is at least as difficult as all problems in NP and at least as difficult as all problems in coNP.
MSC:
90C31 | Sensitivity, stability, parametric optimization |
90C27 | Combinatorial optimization |
68Q25 | Analysis of algorithms and problem complexity |
90C60 | Abstract computational complexity for mathematical programming problems |
Citations:
Zbl 0895.90155References:
[1] | Blair, C., Sensitivity analysis for knapsack problems: a negative result, Discrete Appl. Math., 81, 133-139 (1998) · Zbl 0895.90155 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.