| Thursday, March 26th, 2015 | 4pm-5pm | Burnside 719A |
Bilevel knapsack problems are among the most natural extensions of combinatorial optimization problems to their bilevel counterpart. In particular, several variants of bilevel knapsack problems have been recently proposed in the literature and all of them have appealing applications ranging from finance to tax management. We discuss three of these variants and we argue that, surprisingly, their complexity might vary both in theory and in practice quite drastically. Moreover, we give for one of these variants involving interdiction constraints a polynomial time approximation scheme, which is a rather surprising result in the area. Finally, we discuss how to solve the problems in practice. (Joint work with Alberto Caprara, Margarida Carvalho, Gerhard Woeginger).