

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。