On a Class of Interdiction Problems with Partition Matroids: Complexity and Polynomial-Time Algorithms
研究了一类线性拟阵阻断问题，其中上下层决策者受不同划分拟阵约束，证明该问题在二进制权重下是NP难的，但若容量约束数量固定则有多项式时间算法。
In this study, we consider a class of linear matroid interdiction problems, where the feasible sets for the upper-level decision maker (referred to as a leader) and the lower-level decision maker (referred to as a follower) are induced by two distinct partition matroids with a common weighted ground set. Unlike classical network interdiction models where the leader is subject to a single budget constraint, in our setting, both the leader and the follower are subject to several independent capacity constraints and engage in a zero-sum game. Although the problem of finding a maximum weight independent set in a partition matroid is known to be polynomially solvable, we prove that the considered bilevel problem is NP-hard even when the weights of ground elements are all binary. On a positive note, it is revealed that, if the number of capacity constraints is fixed for either the leader or the follower, then the considered class of bilevel problems admits several polynomial-time solution schemes. Specifically, these schemes are based on a single-level dual reformulation, a dynamic programming-based approach, and a greedy algorithm for the leader. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.