Document Zbl 0957.90124

Sensitivity analysis for knapsack problems: Another negative result. (English) Zbl 0957.90124

Discrete Appl. Math. 92, No. 2-3, 247-251 (1999).

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.

Cited in 7 Documents

MSC:

90C31	Sensitivity, stability, parametric optimization
90C27	Combinatorial optimization
68Q25	Analysis of algorithms and problem complexity
90C60	Abstract computational complexity for mathematical programming problems

Keywords:

sensitivity analysis; computational complexity; adjacent knapsack problems

Citations:

Zbl 0895.90155

Cite Review PDF

Full Text: DOI

References:

[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.