A simple $(2+ε)$-approximation for knapsack interdiction
2026-04-23 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a problem where you want to remove some items within a budget to reduce the highest possible profit from the leftover items fitting in a knapsack with limited capacity. They provide a simpler and faster approximation algorithm that guarantees a solution close to twice the optimal. Their method also extends to cases where the knapsack has multiple capacity constraints. This work improves on previous methods by offering easier implementation while maintaining good accuracy.
knapsack probleminterdictionapproximation algorithmpolynomial-time approximation scheme (PTAS)capacity constraintprofit maximizationbudget constraintmulti-dimensional knapsack
Authors
Noah Weninger
Abstract
In the knapsack interdiction problem, there are $n$ items, each with a non-negative profit, interdiction cost, and packing weight. There is also an interdiction budget and a capacity. The objective is to select a set of items to interdict (delete) subject to the budget which minimizes the maximum profit attainable by packing the remaining items subject to the capacity. We present a $(2+ε)$-approximation running in $O(n^3ε^{-1}\log(ε^{-1}\log\sum_i p_i))$ time. Although a polynomial-time approximation scheme (PTAS) is already known for this problem, our algorithm is considerably simpler and faster. The approach also generalizes naturally to a $(1+t+ε)$-approximation for $t$-dimensional knapsack interdiction with running time $O(n^{t+2}ε^{-1}\log(ε^{-1}\log\sum_i p_i))$.