A complexity and approximability study of the bilevel knapsack problem

Thumbnail Image
Date
2013
Authors
Caprara,A
Maria Margarida Carvalho
Lodi,A
Woeginger,GJ
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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). © 2013 Springer-Verlag.
Description
Keywords
Citation