A Study on the Computational Complexity of the Bilevel Knapsack Problem
From MaRDI portal
Publication:3192105
DOI10.1137/130906593zbMath1297.90134OpenAlexW2046432398MaRDI QIDQ3192105
Gerhard J. Woeginger, Margarida Carvalho, Andrea Lodi, Alberto Caprara
Publication date: 26 September 2014
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://research.tue.nl/nl/publications/275b26fb-dcdb-47f1-abec-b06339952892
computational complexityknapsack problembilevel programmingpolynomial hierarchyapproximation schemeapproximability
Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Complexity of the multilevel critical node problem, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, The robust bilevel continuous knapsack problem with uncertain coefficients in the follower's objective, Observability of power systems with optimal PMU placement, Computing equilibria for integer programming games, A faster algorithm for the continuous bilevel knapsack problem, Solution techniques for bi-level knapsack problems, A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints, Mixed integer bilevel optimization with a \(k\)-optimal follower: a hierarchy of bounds, A survey on mixed-integer programming techniques in bilevel optimization, An exact method for binary fortification games, On Bilevel Optimization with Inexact Follower, Mixed-integer bilevel representability, Interdiction Games and Monotonicity, with Application to Knapsack Problems, Complexity of near-optimal robust versions of multilevel optimization problems, A dynamic reformulation heuristic for generalized interdiction problems, On the Stackelberg knapsack game, Algorithms and applications for a class of bilevel MILPs, The subset sum game revisited, Computational complexity characterization of protecting elections from bribery, The trouble with the second quantifier, A Stackelberg knapsack game with weight control, Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography
