Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
A simple -approximation for knapsack interdiction
Noah Weninger
In the knapsack interdiction problem, there are items, each with a non-negative profit, interdiction cost, and packing weight. There is also an interdiction budget and a capaci…
cs.DS2024
Interdiction of minimum spanning trees and other matroid bases
Noah Weninger, Ricardo Fukasawa
In the minimum spanning tree (MST) interdiction problem, we are given a graph with edge weights, and want to find some satisfying a knapsack constraint suc…
cs.DS2022
A Knapsack Intersection Hierarchy Applied to All-or-Nothing Flow in Trees
Adam Jozefiak, F. Bruce Shepherd, Noah Weninger
We introduce a natural knapsack intersection hierarchy for strengthening linear programming relaxations of packing integer programs, i.e., where…