A simple $(2+\epsilon )$-approximation for knapsack interdiction

Noah Weninger

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 capaci…