Approximation Algorithms for the Bounded Knapsack Interdiction Problem

In this paper, we consider a bounded knapsack interdiction problem. Given a set \(N=\{1,2,\cdots ,n\}\) $N=\{1,2,\cdots ,n\}$ of item types and a knapsack, there are \(b_j\) $b_j$ identical copies of items for type j available, where all items of type j have a profit \(p_j\) $p_j$ and a weight \(w_j\) $w_j$ . Each item type also has an interdiction cost. The goal is to remove a subset of the item types constrained to a budget, such that the maximum profit of the bounded knapsack problem in the remaining item types is minimized. We first present a simple \((3+\varepsilon )\) $(3+\epsilon )$ -approximation algorithm with running time \(O(n^2)\) $O(n^2)$ when \(b_j=1\) $b_j=1$ of each item type for any \(\varepsilon >0\) $\epsilon >0$ . Then, we propose a polynomial time approximation scheme for the bounded knapsack interdiction problem.