Monday, March 23, 2026 12:30 pm
-
1:30 pm
EDT (GMT -04:00)
Abstract:In the knapsack interdiction problem, there are two players and $n$ items, each with some profit, removal cost, and packing weight. First, the interdictor selects items to remove; the total removal cost must fit within the interdiction budget. Then, the follower solves a knapsack problem on the remaining items. The objective is to select an interdiction set which minimizes the follower's maximum profit. This problem is $\Sigma_2^p$-complete. We present a $(2+\epsilon)$-approximation with running time polynomial in $n$ and $1/\epsilon$. We start by showing that after LP-relaxing the follower's knapsack, the problem becomes solvable with dynamic programming in pseudopolynomial time, and yields a 2-approximation for the original problem. We then show that this dynamic program can be rounded to get an FPTAS for the 2-approximate problem. Although there is already a PTAS known for knapsack interdiction (Chen et al, 2022), our algorithm is considerably simpler and faster: to achieve a 3-approximation, the PTAS needs running time $\Omega(n^{100})$, whereas ours is only $\tilde O(n^3)$. |