A Note on Interdiction of Linear Minimization Problems
Provides a unified theoretical framework for interdiction problems, but is primarily a conceptual note without experimental validation or concrete performance numbers.
The paper isolates a general argument from a specific FPTAS for connectivity interdiction, showing that interdiction of linear minimization problems reduces to optimizing a reweighted objective and enumerating its 2-approximate minimizers. This yields an exact algorithm when the reweighted problem can be optimized and its approximate minimizers enumerated.
Motivated by the FPTAS for connectivity interdiction of Huang et al. (IPCO'24), we isolate the part of the argument that does not use cuts. The setting is a minimization problem over a feasible-set family $\mathcal F$ with a linear objective $w(S)=\sum_{e\in S}w(e)$. After dualizing the interdiction budget, deletion can be absorbed into truncated weights $w_λ(e)=\min\{w(e),λc(e)\}$. At an optimal Lagrange multiplier $λ^*$, the unknown optimal interdiction witness is a strict $2$-approximate minimizer of the reweighted problem. Thus an exact algorithm can be obtained whenever one can optimize $w_{λ^*}$ over $\mathcal F$, enumerate all its $2$-approximate minimizers, and solve the remaining knapsack problem.