Noah Weninger

Interdiction of minimum spanning trees and other matroid bases

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories 0-1 Programming, Dynamic Programming, Graphs and Matroids Tags , , , , , ,

    \(\) In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this … Read more

    A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Dynamic Programming Tags , , , ,

    \(\) We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and \(n\) items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of … Read more