In this contribution we pursue the study of the Bi-level Interdiction Knapsack Problem, where a leader interdicts some knapsack items subject to a budget constraint in order to maximally reduce the total profit of the Knapsack Problem that the follower solves on the remaining items. We study the computational complexity of the problem when the leader’s interdiction costs are unitary and prove that the problem remains \(\Sigma _2^p\) -complete using a reduction from the bi-level 3-SAT problem. Additionally, we prove that the version with unitary lower level weights but arbitrary interdiction costs is NP-complete.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Complexity Results on the Bi-Level Interdiction Knapsack Problem with Unit Interdiction Costs or Unit Weights

  • Alberto Boggio Tomasaz,
  • Margarida Carvalho,
  • Roberto Cordone,
  • Pierre Hosteins

摘要

In this contribution we pursue the study of the Bi-level Interdiction Knapsack Problem, where a leader interdicts some knapsack items subject to a budget constraint in order to maximally reduce the total profit of the Knapsack Problem that the follower solves on the remaining items. We study the computational complexity of the problem when the leader’s interdiction costs are unitary and prove that the problem remains \(\Sigma _2^p\) -complete using a reduction from the bi-level 3-SAT problem. Additionally, we prove that the version with unitary lower level weights but arbitrary interdiction costs is NP-complete.