期刊
SIAM JOURNAL ON OPTIMIZATION
卷 24, 期 2, 页码 823-838出版社
SIAM PUBLICATIONS
DOI: 10.1137/130906593
关键词
bilevel programming; knapsack problem; computational complexity; polynomial hierarchy; approximability; approximation scheme
资金
- DIAMANT (a mathematics cluster of the Netherlands Organisation for Scientific Research NWO)
- Alexander von Humboldt Foundation, Bonn, Germany
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).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据