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 ̸= NP).
A Study on the Computational Complexity of the Bilevel Knapsack Problem / Alberto Caprara;Margarida Carvalho;Andrea Lodi;Gerhard J. Woeginger. - In: SIAM JOURNAL ON OPTIMIZATION. - ISSN 1052-6234. - STAMPA. - 24:(2014), pp. 823-838. [10.1137/130906593]
A Study on the Computational Complexity of the Bilevel Knapsack Problem
CAPRARA, ALBERTO;LODI, ANDREA;
2014
Abstract
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 ̸= NP).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.