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).
Original language | English |
---|---|
Title of host publication | Integer Programming and Combinatorial Optimization (16th International Conference, IPCO 2013, Valparaíso, Chile, March 18-20, 2013. Proceedings) |
Editors | M. Goemans, J. Correa |
Place of Publication | Berlin |
Publisher | Springer |
Pages | 98-109 |
ISBN (Print) | 978-3-642-36693-2 |
DOIs | |
Publication status | Published - 2013 |
Event | 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013) - Valparaíso, Chile Duration: 18 Mar 2013 → 20 Mar 2013 Conference number: 16 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 7801 |
ISSN (Print) | 0302-9743 |
Conference
Conference | 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2013) |
---|---|
Abbreviated title | IPCO 2013 |
Country/Territory | Chile |
City | Valparaíso |
Period | 18/03/13 → 20/03/13 |