Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.23334 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910166123806720 |
|---|---|
| author | Cong, Yu Tian, Kangyi |
| author_facet | Cong, Yu Tian, Kangyi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23334 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Note on Interdiction of Linear Minimization Problems Cong, Yu Tian, Kangyi Data Structures and Algorithms 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. |
| title | A Note on Interdiction of Linear Minimization Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.23334 |