A Complexity and Approximability Study of the Bilevel Knapsack Problem
A Complexity and Approximability Study of the Bilevel Knapsack Problem
复制标题
双层背包问题的复杂性和逼近性研究
DOI：
10.1007/978-3-642-36694-9_9
复制
发表时间：
2013
期刊：
影响因子：
6
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
A. Caprara;Margarida Carvalho;Andrea Lodi;G. Woeginger
我们分析了三个基本变量的双层背包问题，这一切都是完整的第二层次的多项式。如果背包问题中的权重和利润系数以一元形式编码，则两个双层变体在多项式时间内可解，而第三个是NP完全的。此外，我们设计了一个多项式时间的近似方案，这第三个变量，而其他两个变量不能近似在多项式时间内的任何常数因子（假设P <$NP）。
We analyze three fundamental variants of the bilevel knapsack problem, which all are complete for the second level of the polynomial hierarchy. If the weight and profit coefficients in the knapsack problem are encoded in unary, then two of the bilevel variants are solvable in polynomial time, whereas the third is 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≠NP).