Journal
SIAM JOURNAL ON OPTIMIZATION
Volume 24, Issue 2, Pages 823-838Publisher
SIAM PUBLICATIONS
DOI: 10.1137/130906593
Keywords
bilevel programming; knapsack problem; computational complexity; polynomial hierarchy; approximability; approximation scheme
Categories
Funding
- DIAMANT (a mathematics cluster of the Netherlands Organisation for Scientific Research NWO)
- Alexander von Humboldt Foundation, Bonn, Germany
Ask authors/readers for more resources
We analyze the computational complexity of three fundamental variants of the bilevel knapsack problem. All three variants are shown to be complete for the second level of the polynomial hierarchy. We also discuss the somewhat easier situation where the weight and profit coefficients in the knapsack problem are encoded in unary: two of the considered bilevel variants become solvable in polynomial time, whereas the third becomes NP-complete. Furthermore, we design a polynomial time approximation scheme for this third variant, whereas the other two variants cannot be approximated in polynomial time within any constant factor (assuming P not equal NP).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available