Hardness and approximation for network flow interdiction
From MaRDI portal
Publication:4638580
Abstract: In the Network Flow Interdiction problem an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem despite decades of interest in it. We present the first approximation hardness, showing that Network Flow Interdiction and several of its variants cannot be much easier to approximate than Densest k-Subgraph. In particular, any -approximation algorithm for Network Flow Interdiction would imply an -approximation algorithm for Densest k-Subgraph. We complement this hardness results with the first approximation algorithm for Network Flow Interdiction, which has approximation ratio 2(n-1). We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s-t-Cut problem, and transferring our results gives the first approximation hardness and algorithm for that problem, as well.
Recommendations
- An approximation algorithm for network flow interdiction with unit costs and two capacities
- Network flow interdiction on planar graphs
- Approximation algorithm for maximum flow network interdiction problem
- scientific article; zbMATH DE number 4055051
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- Network interdiction and stochastic integer programming
- Approximation and Online Algorithms
- Flow Problems in Multi-Interface Networks
- On the computational behavior of a polynomial-time network flow algorithm
- Combined Competitive Flow Control and Routing in Networks with Hard Side Constraints
Cited in
(34)- A \((B + 1)\)-approximation for network flow interdiction with unit costs
- Improved Algorithms for MST and Metric-TSP Interdiction
- Protection of flows under targeted attacks
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- On the hardness of approximating the min-hack problem
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- Sherali-Adams integrality gaps matching the log-density threshold
- Maximizing convergence time in network averaging dynamics subject to edge removal
- Packing interdiction and partial covering problems
- Rerouting Flows when Links Fail
- A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid
- Vertex downgrading to minimize connectivity
- Parametric multiroute flow and its application to multilink-attack network
- Symmetric interdiction for matching problems
- Approximability of the k‐server disconnection problem
- scientific article; zbMATH DE number 2050722 (Why is no real title available?)
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- Approximation algorithm for maximum flow network interdiction problem
- Interdicting facilities in tree networks
- The complexity of computing a robust flow
- Network flow interdiction on planar graphs
- Theoretical and computational advances for network diversion
- Matrix interdiction problem
- Improved hardness for cut, interdiction, and firefighter problems
- Interdiction problems on planar graphs
- On short paths interdiction problems: Total and node-wise limited interdiction
- An approximation algorithm for network flow interdiction with unit costs and two capacities
- Blocking optimal structures
- An exact method for nonlinear network flow interdiction problems
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Analysis of budget for interdiction on multicommodity network flows
- Filtering undesirable flows in networks
- The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
- On the minimum \(s-t\) cut problem with budget constraints
This page was built for publication: Hardness and approximation for network flow interdiction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638580)
